We have studied the effect of dynamical correlations on the electronic structure of single Co adatoms on graphene monolayers with a recently develeoped method for nanoscopic materials that combines density-functional calculations with a fully dynamical treatment of the strongly interacting 3d electrons. The coupling of the Co 3d shell to the graphene substate and hence the dynamic correlations are strongly dependent on the orbital symmetry and the system parameters (temperature, distance of the adatom from the graphene sheet, and gate voltage). When the Kondo effect takes place, we find that the dynamical correlations give rise to strongly temperature-dependent peaks in the Co 3d spectra near the Fermi level. Moreover, we find that the Kondo effect can be tuned by the application of a gate voltage. It turns out that the position of the Kondo peaks is pinned to the Dirac points of graphene rather than to the chemical potential.