Le club a été fondé en 2006 sous l'appellation PRK Hekari Souths United FC (PRK pour Petroleum Resources Kutubu)[2],[3]. Par la suite, son nom a évolué plusieurs fois, passant par Hekari United FC ou encore Hekari Souths United FC.
Le club s'impose dès sa création comme une des principales équipes de Papouasie-Nouvelle-Guinée en remportant la première édition du championnat semi-professionnel National Soccer League. Il enchaînera avec 8 titres consécutive de 2007 à 2014[4].
Les Néo-Zélandais partent favoris, mais se font surprendre 3-0 au match aller en Papouasie-Nouvelle-Guinée. Malgré la défaite 2-1 au retour à Auckland, le Hekari United remporte le trophée et se qualifie pour la Coupe du Monde des Clubs 2010 qui se déroule aux Émirats arabes unis. Ils perdent le seul match qu'ils disputent contre le champion local (Al Wahda) par 3-0.
Plus tard, l'équipe petrolique a réussi à dominer le titre de la ligue nationale pendant quatre années consécutives. Le dernier titre en championnat 2014 a été noté que la finale disputée face au Lae FC a été arrêtée à la 70e minute à la suite de violences dans le stade. À ce moment de la partie, Hekari United menait 3-0[5]. Le titre lui a été attribué et le club a donc participé à la Ligue des Champions de l'OFC suivante.
En 2015, le club s'incline en demi-finale du championnat contre le Madang Fox alors qu'il avait terminé la phase régulière du championnat en tête. D'ailleurs, cette première place de la phase régulière lui donne accès à la Ligue des Champions de l'OFC 2016.