W trakcie powstania tajpingów w Chinach brał udział w obronie zagrożonego przez powstańców Szanghaju, nadzorując w maju 1862 budowę fortyfikacji w tym mieście. Po śmierci Fredericka Townsenda Warda przejął chińsko-cudzoziemski oddział o nazwie Armia Zawsze Zwycięska (Armia Niezwyciężona), której Ward był organizatorem i pierwszym dowódcą. Składała się ona z 3500 chłopskich najemników, dowodzonych przez europejskich dowódców. Na jej czele zdobył wiele miast w delcie Jangcy, podał się jednak do dymisji, gdy cesarz Chin zaczął skazywać na śmierć powstańców.
W 1874 z ramienia rządu angielskiego udał się do Egiptu, stopniowo uzależnianego od Anglii. Na skutek próśb ze strony rodaków, Gordon powrócił do Chin, otrzymując najwyższy stopień w armii chińskiej – titu (naczelny wódz), lecz nie wyraził zgody na przyjęcie od chińskiego cesarza 100 000 sztuk złota, czym zyskał opinię człowieka odpornego na korupcję. Uzyskał Order Łaźni. W 1865 powrócił do Anglii, gdzie nie powierzono mu dowództwa nad żadną z jednostek bojowych armii brytyjskiej, lecz przez 5 lat przyszło mu kierować pracami inżynieryjnymi podczas renowacji fortów w Gravesend i Tilbury. W 1873 został awansowany na pułkownika i wysłany do Sudanu, gdzie czekało go objęcie stanowiska gubernatora i misja zwalczania handlu niewolnikami.