The 2004–05 Victoria Salmon Kings season is the Salmon Kings' inaugural season in the ECHL. While the Victoria region has had a long and distinguished hockey history - the Victoria Cougars won the Stanley Cup in 1925 - the region was the largest Canadian region without either professional or Major-Junior hockey when the WHL Victoria Cougars (a team with no connection to the aforementioned Cougars) moved to Prince George in 1994. This was a crippling blow to Victoria hockey fans, whose highest-level remaining local team was the Tier II Junior 'A' Victoria Salsa.
By this time, it had become evident that the 50-year-old Victoria Memorial Arena, seating only 4,000 for hockey, would have to be replaced if Victoria expected to be able to attract a new hockey club. After several years of discussion, the construction of a new arena was approved by Victoria voters in a 2002 referendum, with one key condition being that its construction was dependent on Victoria securing a WHL team. When the private-sector partner, RG Properties, was unable to secure a WHL club, the company bought the rights to the defunct ECHL Baton Rouge Kingfish, formerly the Erie Panthers, a charter member of the ECHL, and announced that Victoria's new team would be named the Salmon Kings.
It became clear as the 2004–05 ECHL season approached that Victoria's new arena, now called the Save-on-Foods Memorial Centre, was not going to be ready in time for the season. In response, the ECHL scheduled the Salmon Kings to begin their inaugural season with an unheard-of 14 game road trip. This was not enough time for the arena to be completed, and in the summer of 2004 the Salmon Kings were forced to secure ice time in the Bear Mountain Arena in the suburban community of Colwood, which had been constructed with the needs of the junior 'A' Victoria Salsa and the Victoria Shamrocks box lacrosse club in mind.
Despite all this, the Salmon Kings took to the ice in their first regular-season game on October 22, 2004, in Bakersfield, California, against the Bakersfield Condors. Former University of Alberta player Ryan Wade scored the first goal in Salmon Kings history. They lost this game 7-2; the Salmon Kings would struggle during their 14-game road trip, only winning 3 games, losing 10 games in regulation and one in a shootout. Their first victory came at the expense of the Fresno Falcons on October 24, which the Salmon Kings won by a convincing 5-0 margin. David Brumby, the Kings' starting goaltender at the time, turned away 37 shots for the shutout.
As the NHL lockout progressed, Dale Purinton and Dan Blackburn of the New York Rangers and Mark Smith of the San Jose Sharks played for the Salmon Kings. Purinton, an enforcer, was suspended twice by the league, the first for a career-ending check into the boards of Condors player Krzysztof Wieckowski, and the second for returning to the ice to fight after being ejected during a bench-clearing brawl involving the Kings and the Falcons. After the latter suspension, Purinton was suspended indefinitely by the Salmon Kings and did not play again that season.
After the grueling 14-game road trip which lasted for over a month, the Salmon Kings finally played their first home game on December 5, 2004, at Bear Mountain Arena. The Salmon Kings lost this game 4-3 in overtime. They would continue to struggle during their first season, going only 15-52-5 over 72 games; notably, they set an ECHL record for a continuous winless streak, going 0-18-2 between December 31, 2004 and February 4, 2005.
The few positives for the team in their inaugural season was Ryan Wade who would be known by fans as "Mr. Salmon King" led the team in scoring (19g-31a) and team captain, Brad Dexter was voted a starter on the National Conference's All-Star Team.