De club is in 2004 speciaal opgericht om als een van de acht startende clubs deel te nemen in de gesloten New Zealand Football Championship (de hoogste divisie). In het eerste seizoen van de New Zealand Football Championship werd de club tweede in de reguliere competitie en bereikte de finale in de play-off, die echter verloren werd van competitiewinnaar Auckland City FC. Waitakere United eindigde in 2007, 2008, 2009 en 2011 als eerste in de reguliere competitie. In 2005 en van 2007-2013 werd telkens de Grand Final bereikt en in 2008, 2010, 2011, 2012 en 2013 ook gewonnen en daarmee de landstitel.
OFC Champions League
Waitakere United won in 2007 de eerste editie van de OFC Champions League (ze namen deel als plaatsvervanger van landskampioen Auckland City die als titelhouder van de voorloper van toernooi, het OFC Club Championship, aan het toernooi deelnam) door in de finale op basis van uitdoelpunten te winnen van Ba FA uit Fiji. Ook de tweede editie van de OFC Champions League (hierin waren beide Nieuw-Zeelandse rollen omgedraaid) werd gewonnen, ze versloegen Kossa FC Honiara uit de Salomonseilanden in de finale.