Primeros años
Gordon nació en Woolwich, Londres, hijo del mayor general Henry William Gordon (1786-1865) y de Elizabeth (Enderby) Gordon (1792-1873). Fue educado en la escuela Fullands, en Taunton, Somerset, y en la Real Academia Militar de Woolwich. Fue comisionado en 1852 como teniente segundo del Cuerpo de Ingenieros Reales, completando su formación en Chatham. Fue ascendido a teniente en 1854.
A Gordon se le asignó primero la construcción de fortificaciones en Milford Haven, Pembrokeshire, Gales. Cuando comenzó la Guerra de Crimea, fue enviado al Imperio ruso, y llegó a Balaklava en enero de 1855. Se le destinó al sitio de Sebastopol y tomó parte en el asalto de la fortaleza desde el 18 de junio hasta el 8 de septiembre. Gordon también participó en la
expedición a Kinburn, y volvió a Sebastopol al final de la guerra. Por sus servicios en Crimea, recibió la medalla de la guerra de Crimea y broche. A raíz de la paz, se le adjuntó a una comisión internacional para demarcar la nueva frontera entre el Imperio ruso y el Imperio otomano en Besarabia. Continuó la topografía, demarcando la frontera en Asia Menor. Gordon volvió a Gran Bretaña a finales de 1858, y fue designado como instructor en Chatham. Fue promovido a capitán en abril de 1859.
