The world of crystallography was forced to reassess its rules about thirty years ago with the introduction of the concept of quasicrystals, solids with rotational symmetries forbidden to crystals, by Levine and Steinhardt (1984) and the discovery of the first examples in the laboratory by Shechtman et al. (1984). Since then, >100 different types of quasicrystals have been synthesized in the laboratory under carefully controlled conditions. The original theory suggested that quasicrystals can be as robust and stable as crystals, perhaps even forming under natural conditions. This thought motivated a decade-long search for a natural quasicrystal, culminating in the discovery of icosahedrite (Al63Cu24Fe13), an icosahedral quasicrystal found in a museum sample consisting of several typical rock-forming minerals combined with exotic rare metal alloy minerals like khatyrkite and cupalite. Here we briefly recount the extraordinary story of the search and discovery of the first natural quasicrystal.