Gordon worked as an engineer repairing various army buildings in Chatham, and repairing the fort at Pembroke. In 1855 he was sent to the Crimean War and took part in the siege of Sebastopol. After the war, Gordon was sent to survey and map the border between Russia and the Romanian principalities of Moldavia and Wallachia. In May 1857 he was sent to map the border between Russia and Turkey. He was awarded a Turkish war medal and the French Legion of Honour. Gordon returned to England at the end of 1858, where he was promoted to major, and took up a post at Chatham.