Diminutif du nom de la franchise. Après 26 ans d’existence, le championnat australien de football (NSL) s’essoufflait avec le départ croissant des meilleurs joueurs australiens vers des ligues étrangères, un accord de télévision désastreux, le manque d’affluence et la baisse de sponsoring qui en a résulté. Un nouveau championnat fermé, A-League, fut donc lancé en 2004 avec 10 franchises, dont 9 basées dans les principales villes australiennes. Mais, comme la NSL l’avait fait en 1999 en favorisant la fondation des Auckland Kingz, la fédération australienne invita à la création d’une franchise en Nouvelle-Zélande, New Zealand Knights à Auckland. Mais, après deux saisons, cette dernière fut dissoute car les résultats étaient catastrophiques (2 fois derniers, 6 victoires en 42 matchs) et donc les affluences aussi. Toutefois, la A-League et la fédération néo-zélandaise souhaitaient conserver cette présence étrangère et une nouvelle franchise fut donc installée.

Après les échecs de quelques candidatures, Terry Serepisos, un promoteur immobilier de Wellington porta un nouveau projet et apporta les garanties financières nécessaires. Le nouveau club de Wellington fut confirmé le 19 mars 2007. Evidemment, il fallait trouver un nom au nouveau club, élément marketing important dans les franchises des nouveaux marchés. Le propriétaire organisa un concours et plus de 250 noms furent proposés par le public le 23 mars 2007. Le Phoenix ressortit devant les autres dont FC Wellington, Wellington United et Wellington City. La liste fut réduite à 6 et une nouvelle consultation fut lancée dans le journal « Dominion Post ». Parmi les lecteurs, le nom classique « FC Wellington » reçut le plus de soutien, mais parmi les autres cinq noms, plus illustrés, « Phoenix » devança les propositions « Wasps » et « Centurions », tandis que « Thunder » et « Crew » étaient les moins populaires. Les participants avaient une idée, tel que l’écrit l’un d’eux « Follow the lead of the best, stick with a traditional name and let a nickname come from the crowd » (Suivez l’exemple des meilleurs, restez avec un nom traditionnel et laissez un surnom venir de la foule). Seulement, ce n’était peut-être pas satisfaisant pour un propriétaire de franchise qui avait besoin de créer une identité plus rapidement avec le public.

Terry Serepisos retint donc « Phoenix » car « Phoenix took my eye and has stayed with me. It symbolises the fresh start, the rising from the ashes and the incredible Wellington support that has come out » (Phoenix a attiré mon attention et est resté avec moi. Il symbolise le nouveau départ, la renaissance des cendres et l’incroyable soutien de Wellington qui s’est manifesté). Le nom faisait appel à la mythologie, ce qui créait un symbole, une identité connue de tous, et faisait référence à la renaissance du football néozélandais après l’échec de la première franchise. Et comme le dira ultérieurement l’un des membres du groupe de supporteurs, Yellow Fever, « There’s always a feeling of hope around the Phoenix » (il y a toujours le sentiment d’un espoir avec le Phoenix).