Exploring graphene quantum dots (GQDs) is an attractive way to design novel optical and electrochemical sensors for fast and reliable detection of toxic heavy metals (HMs), such as Cd, Hg and Pb. There are two main strategies for achieving this: (i) surface modification of an electrochemical working electrode by nanoscale GQDs and (ii) using a GQD solution electrolyte for optical sensing. Further development of these sensing technologies towards reaching or exceeding the WHO permissible limits implies deep understanding of the interaction between GQDs and HMs in different dielectric media. Solvent is expected to be one of the key factors affecting the binding ability of the GQDs to HMs and their electronic and optical properties. Here we show that the solvent-solute interaction changes the geometrical configuration, stability and absorption spectra of zigzag/armchair-edged GQDs after complexation with neutral and charged HM species. We observe physisorption behavior of Cd and Hg adatoms on the sp2 surface with a solvent-mediated enhancement of the binding energy with increasing solvent polarity. For Pb adatoms, an opposite picture is revealed. We find that the solvent effect also manifests itself in weakening of the chemisorption strength in the HM cation-π system with increasing dielectric constant of the solvent. Thus, a solvent engineering strategy based on control of the dielectric permittivity can be a promising approach to reach the desired binding energy in the HM@GQDs and to provide high sensitivity and selectivity of both optical and electrochemical sensors to toxic HMs we are interested in.