Carbon-supported precious metal catalysts are widely used in heterogeneous catalysis and electrocatalysis, and enhancement of catalyst dispersion and stability by controlling the interfacial structure is highly desired. Here we report a new method to deposit metal oxides and metal nanoparticles on graphene and form stable metal-metal oxide-graphene triple junctions for electrocatalysis applications. We first synthesize indium tin oxide (ITO) nanocrystals directly on functionalized graphene sheets, forming an ITO-graphene hybrid. Platinum nanoparticles are then deposited, forming a unique triple-junction structure (Pt-ITO-graphene). Our experimental work and periodic density functional theory (DFT) calculations show that the supported Pt nanoparticles are more stable at the Pt-ITO-graphene triple junctions. Furthermore, DFT calculations suggest that the defects and functional groups on graphene also play an important role in stabilizing the catalysts. These new catalyst materials were tested for oxygen reduction for potential applications in polymer electrolyte membrane fuel cells, and they exhibited greatly enhanced stability and activity.