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 particles5. 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 NASA's Kepler mission, including objects that are comparable in size to the terrestrial planets in the Solar System.