Construction began in 1986 and completed in 1999.
In 1999, as part of the Saskatchewan provincial budget, a project was begun to gravel 30 km of Highway 956.
In September 2005, to celebrate the centennials of Saskatchewan and Alberta, Saskatchewan Premier Lorne Calvert and Alberta Premier Ralph Klein announced a project costing $45 million to connect La Loche and Fort McMurray with an all-season road. The premiers explained that this would create economic and recreational opportunities, as well as improved access to services and schools.
A crushing project and two clearing projects had been initiated by the time the 2006-2007 Saskatchewan Mid-Year Report was released. They were expected to be completed by the end of 2006.
By May 2006, work began on improving Highway 956 as a joint project by the Alberta and Saskatchewan governments to connect La Loche and Fort McMurray.