K-1

W listopadzie 2000 roku na gali K-1 Oceania Star Wars 2000 w Melbourne zmierzył się w pokazowym pojedynku z najbardziej utytułowanym australijskim kick-boxerem w historii, Stanem Longinidisem. Przegrał z nim przez decyzję po 10-rundowej walce, jednak występ ten zaowocował zaproszeniem go na turniej preeliminacyjny K-1 World GP w Melbourne w lutym 2001 roku. Przegrał w finale przez nokaut z wschodzącą gwiazdą K-1, Nowozelandczykiem Markiem Huntem. Pięć miesięcy później doszło w Auckland do walki rewanżowej, w której Graham pokonał Hunta przez decyzję sędziów.

Po rocznej przerwie powrócił na ringi K-1 w 2003 roku. W lipcu wygrał turniej K-1 World GP w Melbourne, dzięki czemu wywalczył sobie prawo startu w gali eliminacyjnej w Osace, podczas której pokonał kończącego karierę Sama Greco. Zwycięstwo to zapewniło mu udział w Finale K-1 WGP w Tokio – turnieju o mistrzostwo K-1. Odpadł w nim w ćwierćfinale, znokautowany przez późniejszego mistrza Remy'ego Bonjasky'ego.

W 2004 roku wygrał turniej Kings of Oceania 2004, pokonując m.in. Pawła Słowińskiego. Rok później zwyciężył również w Kings of Oceania 2005, uzyskując kwalifikację do turnieju K-1 World GP 2006 w Auckland (GP Oceanii), będącego eliminacją do Finału K-1 World GP 2006. W jego ćwierćfinale zmierzył się ze znanym z kontrowersyjnych zachowań Badrem Hari (przed walką doszło do bójki pomiędzy obydwoma zawodnikami). Graham przegrywał pojedynek na punkty, jednak na kilka sekund przed końcem ostatniej rundy zdołał znokautować Marokańczyka swoim markowym kopnięciem opadającym z obrotu, łamiąc mu szczękę. W półfinale spotkał się z Pawłem Słowińskim i przegrał przed czasem na skutek niskich kopnięć.

W sierpniu 2007 roku, podczas K-1 World GP w Hongkongu stoczył walkę rewanżową z Harim. Przegrał przez jednogłośną decyzję sędziów. Był to jego ostatni występ w organizacji K-1.

Po trzyletniej przerwie spowodowanej startami w MMA powrócił do kick-boxingu. 29 sierpnia 2010 roku znokautował Nowozelandczyka Douga Vineya, zdobywając mistrzostwo świata ISKA w wadze ciężkiej. Stracił je, gdy 20 września 2011 roku sam został znokautowany w swojej trzeciej walce z Pawłem Słowińskim.

Mieszane sztuki walki

W 2008 roku podpisał kontrakt z japońską organizacją World Victory Road i zadebiutował w MMA. Na gali Sengoku 1 w Tokio przegrał przez poddanie z byłą gwiazdą PRIDE FC, zapaśnikiem Kazuyuki Fujitą.

Od 2010 roku walczył dla mniejszych australijskich organizacji. W grudniu tego roku na gali Draka 5 stoczył w rosyjskim Chabarowsku pojedynek z niepokonanym od ponad 4 lat zawodnikiem gospodarzy, Aleksandrem Jemieljanienką. Graham niespodziewanie wygrał z faworyzowanym rywalem przez techniczny nokaut w 2. rundzie za pomocą niskich kopnięć.

Podczas kolejnej edycji tej gali, która odbyła się 11 lutego 2012 roku, znokautował doświadczonego Łotysza Konstantina Głuchowa w 1. rundzie.

Pod koniec roku 24 listopada stoczył rewanżowy pojedynek z Gluhovsem. Kolejny raz lepszy był Graham, który znokautował rywala na początku 1. rundy prawym sierpowym i ciosami w parterze. Stawką pojedynku było międzynarodowe mistrzostwo w wadze ciężkiej organizacji Draka.

W latach 2013-2014 walczył dla Bellator MMA. Od 2014 związany z KSW, gdzie pokonywał Marcina Różalskiego (KSW 28) i Mariusza Pudzianowskiego (KSW 32) – obu przed czasem.

Boks

W zawodowym boksie debiutował w 2000 roku. 11 lipca 2015 został mistrzem Australii w wadze ciężkiej pokonując Bena Edwardsa na punkty. W listopadzie 2015 zdobył pas mistrzowski WBO strefy azjatycko-pacyficznej.

Mieszane sztuki walki

• 2012: Międzynarodowy mistrz Draka w wadze ciężkiej
• 2013: Bellator MMA - finalista turnieju wagi ciężkiej

Kick-boxing

• 1999: Mistrz Australii Kyokushin w kat. open
• 2000: Amatorski Mistrz Świata WKBF w wadze superciężkiej
• 2002: Zawodowy Mistrz Świata WKBF w wadze superciężkiej
• 2003: K-1 World Grand Prix w Melbourne – 1. miejsce
• 2004: Kings of Oceania – 1. miejsce
• 2005: Kings of Oceania – 1. miejsce
• 2010: Zawodowy Mistrz Świata ISKA w wadze ciężkiej

Boks

• 2012: Mistrz Stanu New South Wales w wadze ciężkiej
• 2015: Mistrz Australii w wadze ciężkiej
• 2015: Mistrz WBO Asia Pacific w wadze ciężkiej
• 2016: Mistrz WBF w wadze ciężkiej