We consider a generic minimal modification of the Newtonian potential, that is a modification that introduces only one additional dimensional parameter. The modified potential depends on a function whose behavior for large and small distances can be fixed in order to obtain respectively (i) galactic flat rotational curves and (ii) a universal constant acceleration independent of the masses of the interacting bodies (Pioneer anomaly). Then using a dimensional argument we show that the Tully-Fisher relation for the maximal rotational velocity of spiral galaxies follows without any further assumptions. This result suggests that the Pioneer anomalous acceleration and the flat rotational curves of galaxies could have a common origin in a modified gravitational theory. The relation of these results with the Modified Newtonian Dynamics (MOND) is discussed.