We report on first-principles calculations of spin-dependent properties in graphene induced by its interaction with a nearby magnetic insulator (europium oxide, EuO). The magnetic proximity effect results in spin polarization of graphene π orbitals by up to 24%, together with a large exchange-splitting band gap of about 36 meV. The position of the Dirac cone is further shown to depend strongly on the graphene-EuO interlayer. These findings point toward the possible engineering of spin gating by the proximity effect at a relatively high temperature, which stands as a hallmark for future all-spin information processing technologies.