The team was founded in 1992 as the Parkhill Stars. After only one season, the team name was changed to the North Middlesex Stars.
The early years were rough on the North Middlesex Stars. In the team's first thirteen seasons, only 2 years did they have winning records.
In the summer of 2005, the team was on the verge of implosion. The community came together and saved the team.  Since the crisis, the Stars have found new life. In the 2005-06 season, they celebrated their third ever winning record. In the summer of 2006, the OHA Junior Development League dissolved and was replaced by the Southern Ontario Junior Hockey League. Since the formation of the SOJHL, the Stars have been a standout team. In 2006-07, they finished 3rd overall with 30 victories. In 2007-08, they finished 4th overall with 27 victories. And in 2008-09, the Stars celebrated their fourth consecutive winning season with 25 victories and a 4th place finish in the regular season.