Emerging SARS-CoV-2 variants are creating major challenges in the ongoing COVID-19 pandemic. Being able to predict mutations that could arise in SARS-CoV-2 leading to increased transmissibility or immune evasion would be extremely valuable in development of broad-acting therapeutics and vaccines, and prioritising viral monitoring and containment. Here we use in vitro evolution to seek mutations in SARS-CoV-2 receptor binding domain (RBD) that would substantially increase binding to ACE2. We find a double mutation, S477N and Q498H, that increases affinity of RBD for ACE2 by 6.5-fold. This affinity gain is largely driven by the Q498H mutation. We determine the structure of the mutant-RBD:ACE2 complex by cryo-electron microscopy to reveal the mechanism for increased affinity. Addition of Q498H to SARS-CoV-2 RBD variants is found to boost binding affinity of the variants for human ACE2 and confer a new ability to bind rat ACE2 with high affinity. Surprisingly however, in the presence of the common N501Y mutation, Q498H inhibits binding, due to a clash between H498 and Y501 side chains. To achieve an intermolecular bonding network, affinity gain and cross-species binding similar to Q498H alone, RBD variants with the N501Y mutation must acquire instead the related Q498R mutation. Thus, SARS-CoV-2 RBD can access large affinity gains and cross-species binding via two alternative mutational routes involving Q498, with route selection determined by whether a variant already has the N501Y mutation. These mutations are now appearing in emerging SARS-CoV-2 variants where they have the potential to influence human-to-human and cross-species transmission.