The Carleton Place Kings began play in 1969 in the Renfrew-Lanark Junior C Hockey League. Soon after, the league folded and the Kings ended up in the Rideau-St. Lawrence Junior B Hockey League in 1971. This league later became the Eastern Ontario Junior Hockey League. In 2009 it was announced that the team had been granted expansion to the Central Junior A Hockey League. Although the CJHL franchise has a different name, the Legion Kings are still considered the forerunner to the Canadians franchise.
The Canadians played their first Junior A game on September 11, 2009. At home, the Canadians dropped a 4-1 decision to the Nepean Raiders. On September 13, 2009, the Canadians won their first ever CJHL game, defeating the Ottawa Jr. Senators 3-2 in a shootout on the road.
The 2013-14 season was a landmark season for the Canadians. They shattered both the CCHL's wins and points records en route to their first regular season title, falling one win short of shattering the 1972-73 Pembroke Lumber Kings league record for best winning percentage (47-4-4).