An Otahahu junior, Graham played in 29 tests, captaining the Kiwis side in 18 of them and scoring 7 tries from 1977 to 1988. In 1980 when playing in the Brisbane Rugby League premiership for the Norths club, he helped his side to victory in the grand final. That year in the BRL Preliminary Final against Valleys at Lang Park, Brisbane, Graham put a hit on Australian captain Wally Lewis that crushed his oesophagus. At the end of the season he captained the 1980 New Zealand rugby league tour of Great Britain and France. In a trans-Tasman test at Lang Park on 18 June 1985, while serving as Kiwi captain Graham was deliberately taken out of the game by a high shot from Noel "Crusher" Cleal while playing brilliantly and inspirationally. After winning premierships with his club in New Zealand he played two seasons in the Brisbane Rugby League premiership with the Norths club under coach Graham Lowe, winning the BRL premiership in his second year there, as well as the New South Wales Rugby League premiership for the North Sydney Bears between 1981 and 1988. He also captained the Bears. In what was the last match of the 1988 Great Britain Lions tour, Graham played at second-row forward for the Kiwis in their victory, which saw them qualify for the final of the final of the 1985–1988 World Cup against Australia. In that match Graham also played at second-row forward, but New Zealand were unable to defeat the Kangaroos. At the end of the 1988 Winfield Cup season, Graham travelled to England to captain the newly promoted Wakefield Trinity club in the 1988–89 Rugby Football League season. In 1989 his biography Mark my words: The Mark Graham Story was published. In 2019, Graham spoke of how he ended up at North Sydney saying "I was due to meet with Ken McCaffery one Sunday afternoon in Brisbane. That morning, I went to church and he was there … so that was a good start. Then he called me when I was touring England with the Kiwis in 1980 and offered me $15,000. I said if you double it, I’ll agree this minute. He did … and I realised then I could have made a lot more!, But the joke was on him - what he didn’t realise is that I would have played for nothing. My first contract at Brisbane Norths, I signed the back of a coaster in the pub and they gave me $500... Money never meant much to me".
Post playing
In 1995 Graham was one of the initial inductees of the NZRL Legends of League. The following year he was inducted into the New Zealand Sports Hall of Fame. He went on to coach the Auckland Warriors in the National Rugby League for two seasons in 1999 and 2000. He later became defensive coach for the Japanese rugby union club, Kintetsu. In August 2006 Graham was named at in the North Sydney Bears' Team of the Century. In 2007, he was named at second row in the New Zealand KiwisTeam of the Century and also further honoured as New Zealand's rugby leaguePlayer of the Century. He is an Auckland Rugby League Immortal. In 2008, Graham was also named at second-row in a Norths Devils all-time greatest team. In July 2018, it was announced that Graham would be inducted into the Australian Rugby League Hall of Fame. Mark Graham now lives in Gladstone where he is an Australian Workers' Union delegate at the Gladstone Ports Corporation.
