The abundance of heavy elements (metallicity) in the photospheres of stars similar to the Sun provides a fossil record of the chemical composition of the initial protoplanetary disk. Metal-rich stars are much more likely to harbour gas giant planets, supporting the model that planets form by accumulation of dust and ice particles. Recent ground-based surveys suggest that this correlation is weakened for Neptunian-sized planets. However, how the relationship between size and metallicity extends into the regime of terrestrial-sized exoplanets is unknown. Here we report spectroscopic metallicities of the host stars of 226 small exoplanet candidates discovered by NASAs Kepler mission, including objects that are comparable in size to the terrestrial planets in the Solar System. We find that planets with radii less than four Earth radii form around host stars with a wide range of metallicities (but on average a metallicity close to that of the Sun), whereas large planets preferentially form around stars with higher metallicities. This observation suggests that terrestrial planets may be widespread in the disk of the Galaxy, with no special requirement of enhanced metallicity for their formation.