Czasy Piotra Wielkiego Gordon poznał czternastoletniego wówczas Piotra I jeszcze przed wyjazdem do Anglii. W 1688 regiment Gordona przeniesiono do Kołomienskiego, rezydencji Piotra koło Moskwy, gdzie generał nawiązał bliskie stosunki z przyszłym reformatorem Rosji. Od tej chwili był zawsze u jego boku, nieomal jako zastępczy ojciec: czynnie pomógł carowi w czasie przewrotu roku 1689, który odsunął od władzy regentkę Zofię Aleksiejewną, w 1694 pojechał wraz z carem do Archangielska na manewry floty rosyjskiej i został przy tej okazji mianowany kontradmirałem. Walnie przyczynił się do zdobycia Azowa na Turkach w 1696 i jako jego gubernator ufortyfikował tę twierdzę (1697). Po wyjeździe Piotra na 18-miesięczną podróż do Europy Zachodniej, tzw. „wielkie poselstwo”, Gordon pełnił wysoką funkcję generalnego inspektora rosyjskich sił zbrojnych i stłumił w krwawy sposób wybuchły w 1698 bunt strzelców, którzy mieli powiązania z obaloną regentką Zofią, za co po powrocie Piotra otrzymał w nadanie nowe majątki oraz medal.