The club has its roots in the former Conception Bay Ceebees, a very successful hockey club in the Newfoundland Senior Hockey League from 1958 to 1969. The CeeBee Stars were founded in 2003 and joined the Avalon East Senior Hockey League. The Stars won six straight AESHL championships from 2006 to 2011 and are four-time winners of the Herder Memorial Trophy, emblematic of Newfoundland senior hockey supremacy.
The CeeBee Stars rejoined the Avalon East Senior Hockey League for the 2015-16 season. In September 2015, AESHL was granted senior A status by Hockey Newfoundland and Labrador. The AESHL champions will play the CWSHL champions for the Herder Memorial Trophy beginning in March 2016.