Monolayer graphene exhibits many spectacular electronic properties, with superconductivity being arguably the most notable exception. It was theoretically proposed that superconductivity might be induced by enhancing the electron-phonon coupling through the decoration of graphene with an alkali adatom superlattice [Profeta G, Calandra M, Mauri F (2012) Nat Phys 8(2): 131-134]. Although experiments have shown an adatom-induced enhancement of the electron-phonon coupling, superconductivity has never been observed. Using angle-resolved photoemission spectroscopy (ARPES), we show that lithium deposited on graphene at low temperature strongly modifies the phonon density of states, leading to an enhancement of the electron-phonon coupling of up to λ ≃ 0.58. On part of the graphene-derived π∗-band Fermi surface, we then observe the opening of a Δ ≃ 0.9-meV temperature-dependent pairing gap. This result suggests for the first time, to our knowledge, that Li-decorated monolayer graphene is indeed superconducting, with Tc ≃ 5.9 K.