The discovery of two-dimensional electron gases (2DEGs) at the heterointerface between two insulating perovskite-type oxides, such as LaAlO3 and SrTiO3, provides opportunities for a new generation of all-oxide electronic and photonic devices. However, significant improvement of the interfacial electron mobility beyond the current value of approximately 1,000 cm2V-1s-1 (at low temperatures), remains a key challenge for fundamental as well as applied research of complex oxides. Here, we present a new type of 2DEG created at the heterointerface between SrTiO3 and a spinel {gamma}-Al2O3 epitaxial film with excellent quality and compatible oxygen ions sublattices. This spinel/perovskite oxide heterointerface exhibits electron mobilities more than one order of magnitude higher than those of perovskite/perovskite oxide interfaces, and demonstrates unambiguous two-dimensional conduction character as revealed by the observation of quantum magnetoresistance oscillations. Furthermore, we find that the spinel/perovskite 2DEG results from interface-stabilized oxygen vacancies and is confined within a layer of 0.9 nm in proximity to the heterointerface. Our findings pave the way for studies of mesoscopic physics with complex oxides and design of high-mobility all-oxide electronic devices.