Marcus joined the Rhinos from NRL side Melbourne Storm for the 2004 season and became an instant hit with the Leeds fans. He made his first appearance in a Leeds shirt in the Boxing Day Festive Challenge against Castleford Tigers, scoring a try before making his full debut on the opening day of Super League IX against London Broncos. He marked the occasion with a hat trick and announced his arrival. He capped off a fine debut season in the Grand Final Eliminator when his hat trick booked the Rhinos place at Old Trafford.

In 2005, Bai was again in outstanding form for the Rhinos scoring 19 tries in 32 games in all competitions including a try in the Powergen Challenge Cup Final against his old club, Hull.
In 63 games for the Rhinos he scored an incredible 45 tries including four hat tricks of which two have been against London. He is one of only seven players to win a Grand Final in both Australia and Great Britain. Marcus left the Rhinos at the end of 2005 season, having played his final game against Bradford in the Grand Final.

Marcus joined Melbourne Storm at the inauguration of the club and went on to make over 150 first grade games, a club record and he also set an all-time Storm record for most tries scored with 70. 

He holds the record for most first grade appearances by a Papua New Guinean in the NRL which is remarkable considering he never played junior rugby league He began his career with Port Moresby Vipers, playing two seasons before representing PNG in the 1995 World Cup in tests against New Zealand and Tonga, scoring the only try for PNG against New Zealand, a 60-metre effort. He added a further three tests in 1996 versus Great Britain (1) and New Zealand (2) before moving to England to make eight appearances with Hull in England in 1997. He returned to Australia to sign for Gold Coast and played the final 18 games of the season for five tries and was selected to represent the Rest of the World against the ARL Test side mid-year alongside the likes of Gary Connolly, Jason Robinson and Craig Innes.

At the end of that year he moved to the newly formed Storm and was one of the standouts for the Storm in 1998 finishing with 12 tries and two more in the finals. He was named Dally M Winger of the Year at the end of the season and scored 12 tries, including one in the finals, again in 1999 when he was one of only four players to have played every game for the Storm in 1999.

A season of promise in 2000 wound up a little disjointed for Marcus, missing 10 games through injury, suspension and Olympic Torch duties however it was a round eight arm injury that threatened to end Marcus’ season after slicing his right arm on steel ground signage near the tryline however remarkably he still finished with 13 tries. 

He represented his native Papua New Guinea at the 2000 World Cup and played in all four matches, scoring three tries. In 2001 he suffered a partial tear of the posterior cruciate ligament in his right knee but still managed 11 tries from 21 games.