Oferta złożona przez Dona Mathesona była kontynuacja oferty Northern Thunder FCNorth Qld FC confident of success. The World Game, [dostęp 18 sierpnia 2008]. otrzymała wstępną licencję na udział w rozgrywkach A-League w dniu 24 lipca 2008 rokuNorth Queensland FC awarded exclusive negotiating status. Football Federation Australia, [dostęp 16 sierpnia 2008].. W dniu 28 sierpnia 2008 roku oferta została ostatecznie zaakceptowana przez dyrektora generalnego FFA Bena Buckleya w wyniku spełnienia wszystkich wymogów prawnychA–league.com, [dostęp 16 września 2008]..
6 listopada 2008 została zatwierdzona oficjalna nazwa klubu North Queensland Fury FCNorth Queenland Fury Launched. FourFourTwo, [dostęp 9 marca 2012]..
Debiut w A-League nastąpił w 8 sierpnia 2009 roku, na stadionie Willows Sports Complex. North Queensland Fury uległo w debicie drużynie Sydney FC 2:3. Pierwszym szkoleniowcem zespołu z Townsville był Ian Ferguson. W pierwszym sezonie North Queensland zajął 7. miejsce.