He saw active service on the Niagara frontier in 1864, and was an officer with the 19th Lincoln Battalion of Infantry involved in repelling the Fenian raids of 1866.

When the North-West Rebellion broke out in 1885, McMillan became a Major with the newly formed 95th Battalion of Infantry (Manitoba Grenadiers) and later was promoted to Lieutenant Colonel on June 17, 1887.

He established a milling and grain business in Winnipeg in 1874, and oversaw the first shipment of western Canadian wheat to Minneapolis shortly thereafter.

In 1879, he ran for the Manitoba legislature in the riding of Winnipeg against Thomas Scott, the leader of the opposition to John Norquay's government.

Thomas Greenway's Liberals were called to form a government in January 1888, and won a landslide majority in a general election held later in the year.

McMillan was returned to parliament for the riding of Winnipeg Centre in this election, defeating Conservative Thomas Gilroy by 972 votes to 470.