Valleyite, Ca4(Fe,Al)6O13, is a new sodalite-type mineral discovered in late Pleistocene basaltic scoria from the Menan Volcanic Complex near Rexburg, Idaho, U.S.A. It is an oxidation product of basaltic glass during the early stage of the scoria formation and is associated with hematite (α-Fe2O3), maghemite (γ-Fe2O3), luogufengite (ε-Fe2O3), and quartz on the surface of vesicles. The measured crystal size of valleyite ranges from ~250 to ~500 nm. The empirical chemical formula of valleyite is (Ca3.61Mg0.39)(Fe3.97Al1.91Ti0.09)O13. The mineral has a space group of I4̅3m. The (Fe,Al)-O bond distance and unit-cell edge are slightly larger than those reported for synthetic Ca4Al6O13, presumably due to the presence of the larger Fe3+ cations, compared with Al3+, in the structure. Density functional theory calculations predict that valleyite may be a metastable phase at low temperatures. Measured Curie temperatures for valleyite and luogufengite are 645 and 519 K, respectively. Their magnetization hysteresis loop indicates the magnetic exchange coupling between valleyite (soft magnet) and luogufengite (hard magnet) that aids in the understanding of magnetic properties and paleo-magnetism of basaltic rocks. This new mineral, valleyite, with the sodalite-type cage structure is potentially a functional magnetic material.