Kjølstad maakte zijn wereldbekerdebuut in maart 2002 in Oslo, een jaar later finishte hij in het ZweedseBorlänge voor het eerst in de punten. In december 2004 bereikte hij in de Zwitserse hoofdstad Bern zijn eerste podiumplaats, zes weken later boekte de Noor in Nové Město, Tsjechië zijn eerste wereldbekerzege. Tijdens de Olympische Winterspelen van 2006 in Turijn, Italië eindigde Kjølstad als zevende op de sprint. In december 2007 boekte hij in het FinseKuusamo zijn tweede wereldbekerzege. Op de wereldkampioenschappen langlaufen 2009 in Liberec, Tsjechië sleepte de Noor, achter zijn landgenoot Ola Vigen Hattestad, de zilveren medaille in de wacht op de sprint, later in het toernooi veroverde hij samen met Hattestad de wereldtitel op het onderdeel teamsprint. Tijdens de wereldbekerfinale in Zweden won Kjølstad de sprintetappe in Stockholm.
Noorwegen
Nové Město
Kuusamo
Stockholm
Oberammergau