He served under Lt. Gen. Winfield Scott in the Mexican–American War, earning the brevet of first lieutenant for gallantry at Cerro Gordo.

When the Civil War erupted in 1861, Gordon organized and became colonel of the 2nd Regiment Massachusetts Volunteer Infantry.

The regiment served guarding the upper Potomac River and Frederick, Maryland, and in the spring of 1862, Gordon served under Maj. Gen. Nathaniel P. Banks, unsuccessfully opposing Maj. Gen. Stonewall Jackson in the Shenandoah Valley.

He also took command of 1st Division, XI Corps, following the Battle of Gettysburg and was transferred with it to the Department of the South.

On January 13, 1866, President Andrew Johnson nominated Gordon for the award of the honorary grade of brevet major general, United States Volunteers, to rank from April 9, 1865,[1][2] and the U.S. Senate confirmed the award on March 12, 1866.