The team began play in the 2004–05 season, following the defunct Huntsville Channel Cats of the South East Hockey League. The team finished sixth out of eight teams in the regular season in 2004–05 and lost a one-game playoff to the Jacksonville Barracudas. In 2006, Huntsville finished fifth in the league and was defeated two games to none by the Florida Seals in the second round of playoffs after knocking off the defending league champion Columbus Cottonmouths in three games in the opening round. In 2007, Huntsville's fourth-place regular season finish was for naught as they were swept out of the playoffs by the eventual league champion Fayetteville FireAntz.
In 2008, the Havoc finished last in the SPHL standings and were the only team left out of the league playoffs. Immediately following the conclusion of the season, the team announced it would not renew the contract of head coach John Gibson, who had led the Havoc through all four SPHL seasons, coached the SEHL Channel Cats to the league championship in 2004, and was an All-Star defenseman for the CHL version of the Channel Cats. Eric Soltys was named head coach of the team for the 2008–09 season with Paul Snell serving as his assistant. In the 2008-09 SPHL season the Havoc finished in fourth place. In the 2009 SPHL Playoffs the Havoc was beaten in the first round by the eventual SPHL champions (Knoxville Ice Bears) in 5 games (5 game series). With Randy Murphy taking over coaching duties in 2009–10, the Havoc finished season play in second place, earning a team-record 71 points. The Havoc entered the SPHL playoffs as the #2 seed. In round 1 Huntsville defeated the Pensacola Ice Flyers 2 games to 1. In round 2 the Havoc swept the Knoxville Ice Bears. The Havoc then went on to sweep the Mississippi Surge in the finals, winning their first SPHL President's Cup. In the 2010–11 season, the Havoc finished 3rd in the regular season and lost in the first round of the playoffs to Columbus.