We show that the mass-metallicity relation observed in the local universe is due to a more general relation between stellar mass M*, gas-phase metallicity and SFR. Local galaxies define a tight surface in this 3D space, the Fundamental Metallicity Relation (FMR), with a small residual dispersion of ~0.05 dex in metallicity, i.e, ~12%. At low stellar mass, metallicity decreases sharply with increasing SFR, while at high stellar mass, metallicity does not depend on SFR. High redshift galaxies, up to z~2.5 are found to follow the same FMR defined by local SDSS galaxies, with no indication of evolution. The evolution of the mass-metallicity relation observed up to z=2.5 is due to the fact that galaxies with progressively higher SFRs, and therefore lower metallicities, are selected at increasing redshifts, sampling different parts of the same FMR. By introducing the new quantity mu_alpha=log(M*)-alpha log(SFR), with alpha=0.32, we define a projection of the FMR that minimizes the metallicity scatter of local galaxies. The same quantity also cancels out any redshift evolution up to z~2.5, i.e, all galaxies have the same range of values of mu_0.32. At z>2.5, evolution of about 0.6 dex off the FMR is observed, with high-redshift galaxies showing lower metallicities. The existence of the FMR can be explained by the interplay of infall of pristine gas and outflow of enriched material. The former effect is responsible for the dependence of metallicity with SFR and is the dominant effect at high-redshift, while the latter introduces the dependence on stellar mass and dominates at low redshift. The combination of these two effects, together with the Schmidt-Kennicutt law, explains the shape of the FMR and the role of mu_0.32. The small metallicity scatter around the FMR supports the smooth infall scenario of gas accretion in the local universe.