Decoteau was born on the Red Pheasant Indian Reserve in Saskatchewan on November 19, 1887. One of five children, he was the son of Peter Decoteau and Dora Pambrun. His father, who fought alongside Plains Cree Chief Pitikwahanapiwiyin (Poundmaker) at Battle of Cut Knife in 1885, was an employee of the Indian Department when he was murdered in 1891. With no way to support the family, Decoteau's mother arranged to have the children admitted to the Battleford Industrial School. It was as a student at the school that he first demonstrated an aptitude for athletics.
Decoteau worked as a farm-hand prior to moving to Edmonton where he worked for his brother in law David Latta as a blacksmith. His sister Emily and Latta, a business man and one-time Edmonton alderman, had married in 1899 and Decoteau initially lived with the couple upon his arrival to the city. In 1911 he was hired as a constable by the Edmonton Police, where he served as Canada's first Indigenous officer and was among the city's first motorcycle officers. He promoted to sergeant in 1914.
While in Edmonton he won numerous western Canadian major middle or long distance races. He completed his first race on May 24, 1909, placing second in the one-mile competition. He quickly followed the achievement by winning two five-mile races within six days of each other. The first win occurred at the Edmonton Exhibition, in June, which he completed with a time of 00:28:41. The second was the Mayberry Cup, which took place in Lloydminster on July 1, where he set a new Western record with a time of 00:27:45.
Decoteau competed in the 5,000 metre race at the 1912 Summer Olympics in Stockholm, Sweden serving as the only representative from Alberta on the Canadian Olympic team. Finishing second in the first heat of the 5,000 metres competition, leg cramps impacted his performance in the final run, causing him to finish sixth, overall.
Influenced by his father's involvement with the North-West Rebellion in 1885, Decoteau enlisted in the Canadian Expeditionary Force in April 1916. He first served with the 202nd Infantry Battalion before moving on to the 49th Battalion. Decoteau trained at the Sarcee military training camp, near Calgary, Alberta, from June to October 1917 before being set sail for England. He shipped from Halifax on November 24, 1916 aboard SS Mauretania.
Decoteau continued to run while stationed abroad participating in at least two military personnel athletic competitions. At an event in Salisbury, George V, King of England, awarded Decoteau his personal gold pocket watch as congratulations for winning a 5-mile race. On May 27, 1917 Decoteau, was sent to France along with the other members of the 49th Battalion. While there, his athletic ability was put to use while he served as a communications trench runner.
Decoteau was killed by a German sniper on the morning of October 30, 1917, during the Second Battle of Passchendaele. A common, but unsubstantiated, account of his death suggests that the German sniper stole the pocket watch that had been awarded by George V and was later recovered by his comrades who ensured it was returned to his mother Dora. In 1985, the Cree performed a ceremony in Edmonton "to bring his spirit home". Honours were provided by the Red Pheasant Band, the Edmonton Police Service and the Canadian army.
Recognition of Decoteau's accomplishments is credited to the work of Edmonton police officer Sam Donaghey. After finding a newspaper clipping about Decoteau in 1966, Donaghey conducted research that led to Decoteau's induction into the Edmonton Sports Hall of Fame in 1967 and, later, the Alberta Sport Hall of Fame in 2001. Decoteau's achievements have also been recognized through induction into Saskatchewan Sports Hall of Fame in 2000 and the Canada's Sports Hall of Fame in 2015. The Edmonton Police Museum and Archives contains many of his personal and military trophies and awards.
The City of Edmonton named both a park and a future residential area in Decoteau's honour in 2014. A park located at the northwest corner of 105 Street and 102 Avenue in Downtown Edmonton was named Alex Decoteau Park on September 24, 2014. A future residential area in southeast Edmonton was named Decoteau on October 28, 2014.