В 1985-1989 гг. Йенс Столтенберг возглавлял молодежное крыло Норвежской рабочей партии.
С 1989 по 1990 год Столтенберг работал директором Норвежского статистического института. В это время он поддерживал регулярные контакты с советскими дипломатами, однако прекратил их после получения предупреждения от норвежской службы безопасности о том, что среди его собеседников был агент КГБ.
В 1993-1996гг. - министр торговли и энергетики в правительстве Гру Харлем Брундтланд.
В 1996-1997 гг. - министр финансов в правительстве Турбьерна Ягланда.
3 марта 2000 года Йенс Столтенберг возглавил правительство страны. Кабинет просуществовал немногим более года. На очередных парламентских выборах 10 сентября 2001 года Норвежская рабочая партия получила один из своих самых худших результатов за всю историю, набрав лишь 24% голосов избирателей.
В условиях внутрипартийного кризиса сменил Турбьерна Ягланда на посту председателя партии и возглавил Норвежскую рабочую партию в 2002 году. Смог привести ее к победе на парламентских выборах. По результатам парламентских выборов 12 сентября 2005 года Норвежская партия смогла сформировать правящую коалицию с центристами и Социалистической левой партией.
17 октября 2005 г. - 14 октября 2013 г. - премьер-министр Норвегии.
По результатам парламентских выборов, прошедших 13 сентября 2009 года, Норвежская рабочая партия, вместе со своими союзниками по коалиции, смогла получить незначительное большинство мест в парламенте, что дало возможность Йенсу Столтенбергу вновь сформировать правительство. 20 октября 2009 года Столтенберг представил новый состав кабинета министров страны. Одно из главных отличий нового состава правительства от прежнего - наличие полного гендерного равенства: среди министров десять мужчин и десять женщин.
Столтенберг резко критиковал российскую внешнюю политику еще до назначения на пост Генсека. Так, 25 марта 2014 в речи на конференции Норвежской рабочей партии он заявил, что Россия угрожает безопасности и стабильности в Европе.
После избрания Генеральным секретарем НАТО Столтенберг подчеркнул необходимость наращивания военной мощи альянса, включая ядерное оружие, для сдерживания России от попыток нарушения международных законов и угроз в отношении стран-членов НАТО. Подчеркнул важность соблюдения пятой статьи устава НАТО, предусматривающей совместную оборону и, в особенности, указал на необходимость защиты восточных стран-членов НАТО.