W latach 1685–1686 Gordon przebywał ponownie w Anglii i Szkocji. Odwiedził rodzinne strony w Aberdeenshire i najwyraźniej uzyskał jakieś obietnice nowego króla Jakuba II (w Szkocji Jakub VII), gdyż król zwrócił się do rządzącej wówczas Rosją regentki Zofii Aleksiejewny z prośbą o zwolnienie Gordona ze służby carskiej. Reakcja regentki była bardzo ostra – zagroziła Gordonowi zesłaniem i nakazała go zdegradować do stopnia chorążego. W odpowiedzi Jakub II mianował go posłem angielsko-szkockim w Rosji, ale Zofia Romanowa, uważając że Gordon jest poddanym rosyjskim, nie pozwoliła mu objąć stanowiska. Wkrótce jednak nastroje się uspokoiły, Gordonowi przywrócono stopień generalski. Po kampanii rosyjskiej przeciw Tatarom i Turkom na Krymie awansował nawet na pełnego generała w 1687. W tych czasach Gordon zaprzyjaźnił się z powiernikiem młodego cara Piotra I, Lefortem i wkrótce, za jego pośrednictwem, z samym carem.