Helstad startte zijn carrière bij de lokale club FL Fart. Toen hij in 1995 18 jaar werd, kwam de grootste club van de provincie, de TippeligaenclubHamKam, hem weghalen. Hier speelde hij zo'n drie jaar alvorens hij door SK Brann werd weggehaald
Die Europese club was de Oostenrijkse topclub Austria Wien. Voor zo'n 120.000 euro werd Helstad overgenomen door deze club. Deze periode in zijn carrière moest de periode van bevestiging worden. Ook al won hij in zijn eerste seizoen de titel, beker en supercup, zijn verblijf in Oostenrijk is nooit een groot succes geweest. Na 2 jaar vertrok de speler terug richting Noorwegen.
In augustus 2004 werd Helstad teruggehaald naar Noorwegen om zo zijn carrière te relanceren. Hij deed dit bij een van de concurrenten van zijn ex-club SK Brann voor de titel Rosenborg BK. Bij deze club deed hij zijn eerste ervaring op bij de wereldtop. Hij speelde en scoorde in enkele wedstrijden in de grootste Europese competitie de UEFA Champions League.
In juli2006 keerde Helstad terug naar de club waar hij naam had gemaakt in Noorwegen, SK Brann. Hier lanceerde hij ook weer zijn carrière wat leidde tot een nieuw vertrek naar Europa 2 jaar later. In 2007 won hij de Kniksenprijs voor beste aanvaller.
In 2008 werd hij dan door de Franse eersteklasser Le Mans UC gekocht om het behoud in de Ligue 1 te verzekeren. De Franse club had hiervoor 2 miljoen euro over, wat tot op vandaag nog steeds een top 10-recordbedrag is in de Noorse Tippeligaen.
Het behoud werd echter niet verzekerd, want in mei2010 stond Le Mans UC op een degradatieplaats. Dit weerhield Helstad er niet van bij de club te blijven en in de Ligue 2 mee te strijden.