W służbie trzech władców Rosji Serdecznie przyjęty przez cara Aleksego Michajłowicza, u którego wzbudził zaufanie, Gordon otrzymał jako pierwsze zadanie kierowanie tłumieniem rozruchów roku 1662, spowodowanych pogorszeniem się wartości pieniądza. Wywiązał się z niego i otrzymał w 1666 funkcję nadzwyczajnego posła cara do króla Anglii i Szkocji Karola II, który niedawno był odzyskał swój tron. W Wielkiej Brytanii Gordon pozostał przez prawie dwa lata i spotykał się osobiście z królem. Być może starał się u Stuartów o jakąś funkcję w ojczyźnie i car się o tym dowiedział, gdyż po powrocie do Rosji Gordon popadł w niełaskę: wysłano go w randze pułkownika na Ukrainę na nieznaną bliżej posadę administracyjną. Do czynnej służby wojskowej powrócił w 1677 i walczył w wojskach generała Golicyna pod Czehryniem. Po tej bitwie otrzymał rangę generała-majora (20 sierpnia 1678), zaś już rok później stopień generała-lejtnanta i stanowisko gubernatora Kijowa, mimo że wyprawa do Czehrynia zakończyła się klęską Rosjan i awans Gordona wywołał niechęć prawosławnego patriarchy, który zaczął głosić, że Rosjanie pozostając pod komendą heretyka (tj. katolika), będą zawsze ponosić klęski, gdyż będzie ich za to karał Bóg.