In der Saison 2007/08 nahm man erstmals an der A-League teil, als Nachfolger des Teams New Zealand Knights. In jener Saison wurden 20 Punkte geholt, damit belegte man den letzten Platz. Da es in der A-League keine Absteiger gibt, stand die Ligazugehörigkeit jedoch nicht in Frage. In der zweiten Saison in der A-League wurde das Team Sechster. 2010, 2011, 2012, 2015, 2019, 2020 und 2022 wurden jeweils die Meisterschafts-Play-Offs erreicht. Dabei war das Erreichen des Halbfinales 2010 und 2012 der bisher größte Erfolg. Im australischen FFA Cup 2021 konnte man auch bis ins Halbfinale vordringen. Die Fangemeinde der Phoenix ist bekannt als „Yellow Fever“. Die Heimspiele des A-League Men-Teams werden im Sky Stadium ausgetragen. In der ersten Saison kamen durchschnittlich 12.950 Zuschauer zu den Spielen, was bis heute noch der höchste Schnitt ist.