Near-infrared spectra were obtained for 117 red giants in the Fornax dwarf spheroidal galaxy with the FORS1 spectrograph on the VLT, in order to study the metallicity distribution of the stars and to lift the age-metallicity degeneracy of the red giant branch (RGB) in the color-magnitude diagram (CMD). Metallicities are derived from the equivalent widths of the infrared calcium triplet lines at 8498, 8542, and 8662 Å, calibrated with data from globular clusters, the open cluster M67, and the LMC. For a substantial portion of the sample, the strength of the calcium triplet is unexpectedly high, clearly indicating that the main stellar population of Fornax is significantly more metal-rich than could be inferred from the position of its RGB in the CMD. We show that the relative narrowness of the RGB in Fornax is caused by the superposition of stars of very different ages and metallicities. The region of parameter space occupied by the most metal-rich red giants in Fornax-young, metal-rich, and luminous-is not covered by any of the calibrating clusters, which introduces uncertainty in the high end of the metallicity scale. Using published theoretical calculations of Ca II triplet equivalent widths, we have investigated their sensitivity to luminosity, age, and metallicity. The correlation between absolute I magnitude and Ca II strength appears to be only slightly affected by age variations, and we have used it to estimate the metallicities of the Fornax stars. The metallicity distribution in Fornax is centered at [Fe/H]=-0.9, with a metal-poor tail extending to [Fe/H]~=-2. While the distribution to higher metallicities is less well determined by our observations, the comparison with LMC data indicates that it extends to [Fe/H]~-0.4. By comparing the metallicities of the stars with their positions in the CMD, we have derived the complex age-metallicity relation of Fornax. In the first few gigayears, the metal abundance rose to [Fe/H]~-1.0 dex. The enrichment accelerated in the past ~1-4 Gyr to reach [Fe/H]~-0.4 dex. More than half the sample is constituted of stars younger than ~4 Gyr, thus indicating sustained recent star formation in Fornax. These results are briefly compared with the theoretical predictions on the evolution of dwarf galaxies. They indicate that the capacity of dwarf spheroidal galaxies to retain the heavy elements that they produce is larger than expected. Based on observations collected with the FORS1 instrument on at the European Southern Observatory, Paranal, Chile (ESO 64.N-0421A).