Steele joined the militia in 1866 during the Fenian raids, was a private in the Red River Expedition (1870), joined the Permanent Force Artillery in 1871 and, in 1873, became a sergeant major in the newly created North-West Mounted Police.

A man of enormous physical strength and endurance, Steele managed to be where the action was hottest. He achieved commissioned rank in 1878, acquired his first command at Fort Qu'Appelle in 1879, where he was in charge of police detachments supervising the building of the Canadian Pacific Railway, and was promoted superintendent in 1885. In 1898 he helped establish the authority of the Canadian government during the Klondike Gold Rush.

Steele was given command of Lord Strathcona's Horse in the South African War, and in 1915 he commanded the second Canadian contingent to be sent overseas. In 1916 he was appointed general officer commanding the Shorncliffe area in England, a post he held until the end of the war and his retirement in 1918.