The club was founded in 1901 by Jimmie Enright, owner and manager of the Victoria ice rink in Ottawa. For two seasons, the team only played exhibition matches, without a defeat. For the 1903 season, the team joined the Ottawa City Hockey League, playing against the Beavers, Emmetts, Nationals and Rialto teams. The Victorias won the OCHL championship against the Emmetts at the Rialto Rink. In the 1904 season, the Victorias joined the Canadian Amateur Hockey League (CAHL), junior division. The Victorias defeated Buckingham, Quebec to win the title. For the following season, the Victorias joined the Federal Amateur Hockey League (FAHL), coming second against Smiths Falls for the 1905–06 title.
In the 1906–07 season, the Victorias were involved in the on-ice donnybrook with the Cornwall club that resulted in Bud McCourt's death. Cornwall dropped out of the league and the Victorias were awarded the league title.
After being awarded the 1907 title, the Victorias issued a challenge for the Stanley Cup. The Victorias had to play a qualifying game against Renfrew of the Upper Ottawa League. After defeating Renfrew, the Victorias played the challenge against the Montreal Wanderers, losing the two-game, total-goals series 22 to 4 in January 1908.