When magnetic atoms are inserted inside a superconductor, the superconducting order is locally depleted as a result of the antagonistic nature of magnetism and superconductivity1. Thereby, distinctive spectral features, known as Yu-Shiba-Rusinov states, appear inside the superconducting gap2-4. The search for Yu-Shiba-Rusinov states in different materials is intense, as they can be used as building blocks to promote Majorana modes5 suitable for topological quantum computing6. Here we report the first realization of Yu-Shiba-Rusinov states in graphene, a non-superconducting 2D material, and without the participation of magnetic atoms. We induce superconductivity in graphene by proximity effect7-9 brought by adsorbing nanometer scale superconducting Pb islands. Using scanning tunneling microscopy and spectroscopy we measure the superconducting proximity gap in graphene and we visualize Yu-Shiba-Rusinov states in graphene grain boundaries. Our 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 moments10-14 and constitute the first observation of Yu-Shiba-Rusinov states in a chemically pure system.