Pierwszy sukces na międzynarodowej arenie Johan Kjølstad osiągnął podczas rozgrywanych w 2003 roku mistrzostw świata juniorów w Sollefteå, gdzie zwyciężył w sprincie techniką dowolną. Był to jego jedyny start na imprezie tego cyklu. W Pucharze Świata zadebiutował 13 marca 2002 roku w Oslo, zajmując 48. miejsce w sprincie stylem klasycznym. Pierwsze pucharowe punkty zdobył 20 marca 2003 roku w Borlänge, gdzie w sprincie stylem dowolnym zajął 27. miejsce. Kjølstad sześciokrotnie stawał na podium zawodów PŚ, pierwszy raz dokonał tego 4 grudnia 2004 roku w Bernie, gdzie był trzeci w sprincie stylem dowolnym. W biegu tym wyprzedzili go tylko jego rodak Tor Arne Hetland oraz Thobias Fredriksson ze Szwecji. Nieco ponad miesiąc później, 16 stycznia 2005 roku w Novym Měscie Norweg odniósł swoje pierwsze zwycięstwo wygrywając sprint techniką dowolną. W tej samej miejscowości był także trzeci w tej konkurencji 30 grudnia 2005 roku, a następnie zajmował drugie miejsce 22 stycznia 2006 roku w Oberstdorfie i pierwsze 1 grudnia 2007 roku w Ruce w sprincie klasykiem oraz drugie miejsce w sprincie stylem dowolnym 14 grudnia 2008 roku w Davos. Najlepsze wyniki osiągnął w sezonie 2005/2006, który ukończył na piętnastej pozycji w klasyfikacji generalnej oraz piątej w klasyfikacji sprintu. W 2009 roku wystąpił na mistrzostwach świata w Libercu, gdzie wspólnie z Olą Vigenem Hattestadem został mistrzem świata w sprincie drużynowym. Ponadto na tych samych mistrzostwach zdobył srebrny medal w sprincie indywidualnym stylem dowolnym, ulegając jedynie Hattestadowi. W sprincie stylem dowollnym zajął także siódme miejsce podczas igrzysk olimpijskich w Turynie w 2006 roku. Na rozgrywanych cztery lata później igrzyskach olimpijskich w Vancouver w tej samej konkurencji zajął dziewiąte miejsce. Od 2011 roku startuje także w zawodach FIS Marathon Cup, jednak bez większych sukcesów.