Toimeenpanovaltaa käyttää hallitus. Sen päätehtävänä on laki- ja budjettiehdotusten tekeminen Stortingetille (Norjan kansankäräjät) ja päätösten toimeenpaneminen eri ministeriöiden kautta. Hallitus saa oikeutensa Stortingetiltä ja sitä johtaa pääministeri. Muodollisesti kuningas pyytää enemmistöpuoluetta muodostamaan hallituksen tai elinkelpoisen kokoomuksen.
Hallituksen päätökset tekee muodollisesti kuningas valtioneuvostossa perjantaisin, eli kuningas ja valtioneuvosto hyväksyvät päätökset yhdessä. Kaikkien kuninkaallisten asetusten tulee olla kuninkaan allekirjoittamia ja pääministerin varmentamia.
Norjassa hallituksella, erityisesti pääministerillä, on vähemmän muodollista ja tosiasiallista valtaa kuin monissa muissa länsimaissa. Vaikutusvaltaisimpia paikkoja hallituksessa ovat perinteisesti olleet pääministeri, ulkoministeri ja valtiovarainministeri.
Koska tehtävien määrä on kasvanut, lainsäädäntövaltaa on yhä enemmän siirretty Stortingetiltä hallituksella ja sieltä edelleen alaspäin eri ministeriöille saakka. Norjassa on ministeripohjainen hallitus, jossa kunkin ministeriön johdossa on ministeri. Ministeriä lähimpänä ovat poliittisesti nimitetyt valtiosihteerit, jotka muistuttavat apulaisministereitä, sekä poliittiset neuvonantajat.
Ministeriöillä on hierarkkinen rakenne, jossa ylimpänä on hallinnosta vastaava pääsihteeri, seuraavana osastotasolla ylijohtaja (ekspedisjonssjef) , osasto- tai jaostotasolla apulaisylijohtaja (avdelingsdirektør), jaostotasolla vara-apulaisylijohtaja (underdirektør) ja ryhmätasolla ryhmäpäällikkö (byråsjef). Hierarkiassa viimeisenä ovat virkamiehet, joihin kuuluu eri alojen neuvonantajia, toimeenpanevia virkamiehiä ja toimihenkilöitä.