McMillan was born in Hamilton, Ontario to William and Grace McMillan, both Scottish natives. He attended Hamilton public schools before moving to Detroit, Michigan in 1855 to embark on a career in business. McMillan's first position was as a clerk for Buhl, Ducharme & Co., a wholesale hardware firm. At the age of 20, he left to become the purchasing agent for the Detroit & Milwaukee Railway. In 1863, he helped, along with John Stoughton Newberry, to organize the Michigan Car Company for the manufacture of freight cars. This business grew very rapidly, and in ten years it was one of the largest in the United States. Its success led to the formation of the Detroit Car Wheel Co., the Baugh Steam Forge Co., the Detroit Iron Furnace Co., and the Vulcan Furnace Co. He was also a major shareholder in the Detroit City Railway. McMillan later built and became president of the Duluth, South Shore and Atlantic Railway. He was largely interested in shipbuilding and lake transportation companies. He was one of the largest owners of the Detroit and Cleveland Steam Navigation Co., and the Detroit Transportation Co., and was a director of several banks in Detroit. For three years he was president of the Detroit Board of Park Commissioners and for four years a member of the Detroit Board of Estimates. In 1886, he joined with John S. Newberry in contributing $100,000 each for the maintenance of a hospital in Detroit. McMillan was the only person to be elected Chairman of the Michigan Republican Party three non-consecutive times. He was a presidential elector on the Republican ticket in 1884. He was elected as a Republican to the United States Senate in 1889 and was reelected in 1895 and 1901, serving from March 4, 1889, until his death. He was a dominant figure in the party, leading the business interests especially in opposition to Progressive reformer Governor Hazen S. Pingree in 1897-1900. He was chairman of the Committee on Manufactures in the Fifty-first and Fifty-second Congresses, and of the Committee on the District of Columbia in the Fifty-fourth through Fifty-seventh Congresses. He is also remembered for his chairmanship of the Senate Park Improvement Commission of the District of Columbia, which recommended the redesign of the National Mall to better reflect Pierre Charles L'Enfant's plan for Washington, D.C.. The McMillan Reservoir and the McMillan Sand Filtration Site in DC also bear his name.
