John Millis was born on December 31, 1858, to Walter and Jane Millis, on a farm in Wheatland Township, Michigan. He was appointed to the United States Military Academy at West Point from Michigan in 1877. Millis accepted a commission as 2nd Lieutenant in the Army Corps of Engineers after graduating first in the class of 1881. Early in his career, Millis supervised levee and channel construction on the Mississippi and Red Rivers while stationed in New Orleans, and worked with the Light House Board in Washington, D.C. From 1908 to 1912, he was District Engineer at Cleveland, Ohio, in charge of River and Harbor Works. He then worked as District Engineer at Newport, R.I., Boston, Mass., and the Savannah District. Millis was promoted to Department Engineer, first of the Southeast Department, and then the Central Department in Chicago, Illinois, in 1918. He reached the rank of Colonel before retiring from the Army in 1922.
John Millis married Mary Raoul in 1893, and she traveled with him to his various posts. They had three children, Ralph Millis (1894-1938), historian Walter Millis (1899-1968), and Janet Millis (b. 1903). The couple separated in 1912, and Mary Raoul Millis moved to Atlanta in 1914, where she was an active member of the Socialist Party.