Then moved to the Gold Coast Chargers in Australia. He played the final 18 games of the season scoring 5 tries. That year he was selected to play for the Rest of the World side to play a match against an ARL test side. Although his spell for the Gold Coast was a brief one, it allowed Bai to make a name for himself, while in the process prompting Melbourne Storm to sign him in 1998 in their inaugural season.
He was named Dally M Winger of the Year in his first year at the Melbourne Storm. In his second season for Melbourne, he played in every game, culminating in his appearance on the wing in Melbourne's 1999 NRL Grand Final-winning side. Having won the 1999 Premiership, Melbourne Storm contested in the 2000 World Club Challenge against Super League Champions St Helens RLFC, with Bai playing on the wing and scoring a try in the victory. Bai again represented his country, this time at the 2000 Rugby League World Cup playing in all four of his countries games and scoring three tries. That year for the Storm, Bai was hampered by injuries, including being cut on his right arm by the steel advertising boards. In all he spent six years playing for the Melbourne Storm, playing 144 first grade games and scoring a total of 70 tries.
After displaying his ability with some impressive performances for Melbourne Storm, Bai transferred to English Super League club the Leeds Rhinos. His debut for the club was against Castleford Tigers on the Boxing Day Festive Challenge during which he scored a try after coming off the bench. His full first team debut came against the London Broncos on the opening day of the 2004 Super League season. He announced his arrival at the club in the best possible fashion, by scoring a hat-trick on his full debut in front of the Leeds Rhinos home crowd. Marcus Bai had become an instant hit with the Leeds fans. Later that year in his first full season for Leeds, Marcus Bai scored a hat-trick in the grand final eliminator which helped Leeds on their way to booking their place at Old Trafford. He played for the Leeds Rhinos on the wing in their 2004 Super League Grand Final victory against the Bradford Bulls. As Super League IX champions, the Rhinos faced 2004 NRL season premiers, the Bulldogs in the 2005 World Club Challenge. Bai played on the wing in Leeds' 39-32 victory. Bai played for Leeds in the 2005 Challenge Cup final on the wing and scored a try in their loss against Hull FC.
In 2005, Bai was again impressive making 32 appearances and scoring 19 tries in all competitions. In all he spent two full seasons with Leeds making 63 appearances and scoring 45 tries including four hat-tricks. He is currently just one of seven players to win a Grand Final in the premier Rugby League competitions in both European Super League and Australian National Rugby League. He played for the Leeds Rhinos on the wing in their 2005 Super League Grand Final loss against Bradford Bulls.
Bai left the Leeds Rhinos after spending two successful years with them. He penned a contract with the Bradford Bulls for the 2006 Super League season.
Bai got his Bradford Bulls career off to a good start by scoring two tries on his debut in the 2006 World Club Challenge match against the Wests Tigers in which Bradford won 30-10. At the end of his first season with the Bulls, Marcus was awarded the Best Back of the Year Award by the club. Marcus signed a one-year extension to his contract at Bradford in 2006 which would have kept him at Grattan Stadium until the end of 2007, however in December Marcus announced his retirement from the sport with immediate effect.