The effects of the proximity contact with magnetic insulator on the spin-dependent electronic structure of graphene are explored for the heterostructure of single-layer graphene (SLG) and yttrium iron garnet Y3Fe5O12 (YIG) by means of outermost surface spin spectroscopy using a spin-polarized metastable He atom beam. In the SLG/YIG heterostructure, the Dirac cone electrons of graphene are found to be negatively spin polarized in parallel to the minority spins of YIG with a large polarization degree, without giving rise to significant changes in the π band structure. Theoretical calculations reveal the electrostatic interfacial interactions providing a strong physical adhesion and the indirect exchange interaction causing the spin polarization of SLG at the interface with YIG. The Hall device of the SLG/YIG heterostructure exhibits a nonlinear Hall resistance attributable to the anomalous Hall effect, implying the extrinsic spin–orbit interactions as another manifestation of the proximity effect.