When magnetic atoms are inserted inside a superconductor, the superconducting order is locally depleted as a result of the antagonistic nature of magnetism and superconductivity. Thereby, distinctive spectral features, known as Yu-Shiba-Rusinov states, appear inside the superconducting gap. The search for Yu-Shiba-Rusinov states in different materials is intense, as they can be used as building blocks to promote Majorana modes suitable for topological quantum computing. Here, the first observation of Yu-Shiba-Rusinov states in graphene, a non-superconducting 2D material, and without the participation of magnetic atoms, is reported. Superconductivity in graphene is induced by proximity effect brought by adsorbing nanometer-scale superconducting Pb islands. Using scanning tunneling microscopy and spectroscopy the superconducting proximity gap is measured in graphene, and Yu-Shiba-Rusinov states are visualized in graphene grain boundaries. The results reveal the very special nature of those Yu-Shiba-Rusinov states, which extends more than 20 nm away from the grain boundaries. These observations provide the long-sought experimental confirmation that graphene grain boundaries host local magnetic moments and constitute the first observation of Yu-Shiba-Rusinov states in a chemically pure system.