Conventional in-gap Yu-Shiba-Rusinov (YSR) states require two ingredients: magnetic atoms and a superconducting host that, in the normal phase, has a finite density of states at the Fermi energy. Here we show that hydrogenated graphene can host YSR states without any of those two ingredients. Atomic hydrogen chemisorbed in graphene is known to act as paramagnetic center with a weakly localized magnetic moment. Our calculations for hydrogenated graphene in proximity to a superconductor show that individual adatoms induce in-gap YSR states with an exotic spectrum whereas chains of adatoms result in a gapless YSR band. Our predictions can be tested using state of the art techniques, combining recent progress of atomic manipulation of atomic hydrogen on graphene together with the well tested proximity effect in graphene.