Początki w polityce Nygaardsvold wkrótce stał się liderem lokalnych związków zawodowych i lokalnych struktur Partii Pracy. W 1915 roku został wbrew swojej woli nominowany do wyborów do Stortingu z list Partii Pracy w okręgu Strinda i uzyskał mandat poselski. Choć pierwsze lata w Stortingu nie przynosiły mu satysfakcji, wkrótce Nygaardsvold stał się jedną z wiodących postaci w grupie parlamentarnej Partii Pracy. W latach 1920–1922 był burmistrzem swojego rodzinnego miasta Malvik.
Kiedy w wyniku wyborów w 1927 roku Partia Pracy została najsilniejszą partią w Stortingu, sekretarz partii Martin Tranmæl na stanowisko premiera zaproponował Nygaardsvolda. Nygaardsvold kategorycznie odmówił i zagroził, że zerwie z polityką i wróci na farmę do Hommelviku. To sprawiło, że premierem został starszy i bardziej doświadczony polityk Christopher Hornsrud, a Nygaardsvold, mimo wyraźnej niechęci, objął ministerstwo rolnictwa. Rząd Hornsruda został jednak obalony już po 18 dniach.
Po porażce w wyborach w 1930 roku Partia Pracy zmieniła kurs polityczny. Zamiast rewolucjonizować społeczeństwo, postawiła na walkę z depresją gospodarczą i bezrobociem, zaś Nygaardsvold zrewidował swoje poglądy wobec objęcia stanowiska premiera.