Quasicrystals are solids whose atomic arrangements have symmetries forbidden for periodic crystals, including configurations with five-fold symmetry. All examples identified to date have been synthesized in the laboratory under controlled conditions. Here we present evidence of a naturally-occurring icosahedral quasicrystal that includes six distinct five-fold symmetry axes. The mineral, an alloy of aluminum, copper and iron, occurs as micron-sized grains associated with crystalline khatyrkite and cupalite in samples from the Koryak mountains in Russia. The results demonstrate that quasicrystals can form and remain stable under geologic conditions.