Following his service in the Canadian militia during the Red River Rebellion (1870) and the Northwest Rebellion (1885), he was commissioned as an inspector in the North-West Mounted Police in 1886. After serving in Banff and Regina, he was sent to examine conditions in the Yukon district in 1894 as the government was concerned about the influx of American miners and the liquor trade. He forecast that a gold rush was imminent and reported that there was an urgent need for a police force. In the following year, he went back to the Yukon with a force of 20 men who were in place when the Klondike Gold Rush started in 1897. Constantine's efforts ensured that law was maintained during the gold rush, that Canadian sovereignty was assured and helped create the Mounties' international reputation.
He left the Yukon in 1898, replaced by Sam Steele and returned to the prairies after being promoted to Superintendent. In 1902, he returned to the north to establish forts at Fort McPherson, Northwest Territories and Herschel Island off the Yukon Arctic Ocean coast. This was the first foray by the NWMP north of the Arctic circle.
After returning to the Athabasca District in 1905, Constantine was responsible for building a trail from Fort St. John, British Columbia to Teslin Lake in the Yukon, although work on the trail was abandoned in 1908. He died in 1912 in California following an operation.