Founding under Ted Baer

On May 15, 1999, the USHL unanimously voted to allow then Omaha Lancers' owner, Ted Baer, to place a new team in Kearney, Nebraska, for the 2000–01 season. In June 1999, Jim Hillman was named the team's first head coach. The Tri-City Storm won its first game on September 30, 2000. The Storm finally played its first home game on November 18, 2000, after eight months of construction on the Tri-City Arena. The Storm was named USHL Organization of the Year in its first year of operation.

The Storm narrowly missed the playoffs in its second season. In the following 2002–03 season, during the midst of a 10-game losing streak in mid-December, Jim Hillman resigned as coach and general manager. He was replaced by former Topeka Scarecrows head coach, Bliss Littler, in January. The Storm rallied to make the playoffs with a seven-game win streak down the stretch.

The team had its best season in 2003–04 and won the Anderson Cup for the best regular season record, finishing with a record of 43–12–5 and 91 points. The team featured future National Hockey League players Bill Thomas, Mark Van Guilder, and Peter Mannino. The Storm made its first Clark Cup final, but was eliminated in four games by the Waterloo Black Hawks. Tri-City was named "Organization of the Year" by the USHL for the second time.

Tri-City made the division finals again in the following season despite a fourth place finish in the division. It qualified for the playoffs for the fourth consecutive season, narrowly beating out Sioux City for the final spot in the division. The Storm lost in the opening round playoff series three-games-to-two against the Sioux Falls Stampede.

Organization under Joel Wiens

On May 3, 2006, owner Ted Baer sold the Storm to Joel Wiens after seven years. The Storm finished the 2006–07 regular season with 78 points, giving the team a second place finish in the West Division. The team then won a seven-game series against Sioux City, but was knocked out of the playoffs by the eventual Clark Cup champions, the Sioux Falls Stampede.

The Storm failed to qualify for the playoffs for the first time in six seasons in 2007–08. After the season, head coach and general manager Bliss Littler resigned to accept the head coaching position with the Omaha Lancers. Assistant coach Tom Rudrud was promoted to head coach. The Storm then had their worst season to date, winning just 11 out of 60 games that included a franchise-worst 19-game losing streak.

Brooks' ownership

In April 2009, Wiens sold the arena and team to Las Vegas businessman Kirk Brooks. Brooks announced that Drew Schoneck had replaced Tom Rudrud as head coach. In the 2009–10 season, forward Jaden Schwartz led the league with 50 assists and 83 points. The Storm finished fourth place in the West Division with a 29–25–6 record. The Storm was swept in the first round of the playoffs by former coach Bliss Littler and the Omaha Lancers in three games. The St. Louis Blues selected Schwartz in the first round, 14th overall, the highest Storm selection at that time.

In 2010–11, the Storm finished last in the Western Conference. After another slow start in 2011–12, head coach Drew Schoneck was relieved of his duties and assistant coach Josh Hauge was promoted. Under Hauge, the Storm rallied late in the season and was able to clinch a playoff spot, finishing in sixth in the Western Conference. The Waterloo Black Hawks defeated Tri-City in the first round of the postseason. In Hauge's first full season behind the bench, injuries plagued the Storm and the team again finished last in their conference. Captain Brian Ward had a strong season offensively, scoring 54 points in just 42 games. Mike Vecchione led the team with 26 goals.

After 15 games into the 2013–14 season, Hauge was fired and replaced by Jim Hulton. The team missed the playoffs for the second straight season. The following season, and first full season under Hulton, would lead the Storm to a second place finish within its conference. Tri-City's Chris Wilkie scored 35 goals, tying Rastislav Spirko (2003–04) for the Storm's single-season record. The Storm swept the Omaha Lancers, 3-games-to-0, in the first round. The team then faced Sioux Falls in the conference finals. Led by USHL Rookie of the Year Kieffer Bellows, the Stampede beat the Storm, 3-games-to-1. The Storm won the first game, but before game two, an ice maintenance worker accidentally drilled a hole in a pipe causing water to burst onto the ice. Game Two was postponed from Saturday, April 25 to Wednesday, April 29. After the five-day break, Sioux Falls won three straight games.