The discovery of two-dimensional electron gases at the heterointerface between two insulating perovskite-type oxides, such as LaAlO3 and SrTiO3, provides opportunities for a new generation of all-oxide electronic devices. Key challenges remain for achieving interfacial electron mobilities much beyond the current value of approximately 1,000 cm2V-1 s-1 (at low temperatures). Here we create a new type of two-dimensional electron gas at the heterointerface between SrTiO3 and a spinel g-Al2O3 epitaxial film with compatible oxygen ions sublattices. Electron mobilities more than one order of magnitude higher than those of hitherto-investigated perovskite-type interfaces are obtained. The spinel/perovskite twodimensional electron gas, where the two-dimensional conduction character is revealed by quantum magnetoresistance oscillations, is found to result from interface-stabilized oxygen vacancies confined within a layer of 0.9 nm in proximity to the interface. Our findings pave the way for studies of mesoscopic physics with complex oxides and design of high-mobility all-oxide electronic devices.