Payne werd geboren in Auckland en begon zijn carrière als voetballers dan ook bij Auckland City FC, dat toen uitkwam in de ASB Premiership. In de zomer van 2010 stapte de aanvaller over naar rivaal Waitakere United. Daar speelde hij een belangrijke rol in het succes van de hoogste jeugdteams. Na deelname aan een WK –17 in 2011 speelde Payne op proef bij Blackburn Rovers. Daar verdiende hij een contract voor tweeënhalf jaar.[1] Na afloop van deze verbintenis keerde Payne terug bij Auckland City. Een jaar later verkaste hij naar Portland Timbers, waar hij in het reserveteam ging spelen.[2] Opnieuw bleef de Nieuw-Zeelander een jaar bij zijn club, waarna hij terugkeerde naar zijn vaderland, waar hij voor Eastern Suburbs ging spelen. Hij tekende voor drie jaar. Toen dat contract was afgelopen, nam Wellington Phoenix hem transfervrij over.[3]