The 2001 season was the least successful in the Storm's history, missing the play-offs for the first time. After making a decision to move base from Olympic Park to the larger Colonial Stadium, the club seemed to lack the support, atmosphere and composure they had built up. It reflected in the team's on field performances, losing four of their first six homes games and 7 from their opening 10 overall. Amidst this time the Storm was rocked when coach Anderson quit the club after the 42-18 loss to Parramatta in Round 7.
Along with Richard Swain and Matt Orford, replacement coach Mark Murray lifted the Storm from their bad beginning. Melbourne won seven of their next ten games to reach 6th place on the ladder.
But the bad start had taken its toll, and with the 2001 finals in sight they won only two more games. A last round loss to Canberra saw the Storm finish outside the Top 8.
The 2001 season continued to mark the endurability of Kiwi Test hooker Richard Swain. He was on the field for every minute of the Storm's season and had yet to miss a game for Melbourne in the club's history.