The Mustangs IHC were founded in 2010. During the 2010 AIHL season the Mustangs competed in six exhibition games against ice hockey teams around Australia, including games against the Gold Coast Blue Tongues, the Gold Coast Grizzlys, and Perth Thunder. Following the closure of the 2010 season the AIHL granted a license to the Mustangs to join the league and compete in the 2011 AIHL season. Steve Laforet was named coach and Shane Hardy team captain for the 2011 season. However, on 23 June, it was announced that Laforet had resigned for "personal reasons" and assistant coach, Doug Stevenson would take over the head coach role.
For the start of the 2012 AIHL season the Mustangs changed their name to the Melbourne Mustangs after the AIHL lifted a condition that prohibited the use of "Melbourne" in their team name. The restriction was originally put in place to protect the brand of the Melbourne Ice. . Also the club announced that Bill Wilkinson would be their head coach. Midway through the season though Wilkinson was fired as head coach and replaced by former head coach Steve Laforet. In December 2012 the club announced that they had appointed Brad Vigon as head coach, replacing Steve Laforet who had been fired at the end of the 2012 season. The club also revealed their new logo for the start of the 2013 season featuring a redisigned mustang horse, holding an ice hockey stick.