The promise of graphene and its derivatives as next generation sensors for real-time detection of toxic heavy metals (HM) requires a clear understanding of behavior of these metals on the graphene surface and response of the graphene to adsorption events. Our calculations herein were focused on the investigation of the interaction between three HMs, namely Cd, Hg and Pb, with graphene quantum dots (GQDs). We determine binding energies and heights of both neutral and charged HM ions on these GQDs. The results show that the adsorption energy of donor-like physisorbed neutral Pb atoms is larger than that of either Cd or Hg. In contrast to the donor-like behavior of elemental HMs, the chemisorbed charged HM species act as typical acceptors. The energy barriers to migration of the neutral adatoms on GQDs are also estimated. In addition, we show how the substitution of a carbon atom by a HM adatom changes the geometric structure of GQDs and hence their electronic and vibrational properties. UV-visible absorption spectra of HM-adsorbed GQDs vary with the size and shape of the GQD. Based on our results, we suggest a route towards the development of a graphene-based sensing platform for the optical detection of toxic HMs.