Pohjoismaiden ministerineuvoston sihteeristön organisaatiorakenne on dynaaminen, ja se muuttuu, kun Pohjoismaiden hallitukset tekevät päätöksiä pohjoismaisen yhteistyön uudistamisesta. Sihteeristössä työskentelee satakunta henkeä, jotka tulevat kaikista Pohjoismaista.

Pohjoismaiden ministerineuvoston pääsihteerinä on toiminut 1. tammikuuta 2007 lähtien Islannin entinen pääministeri Halldór Ásgrímsson.

Pohjoismaiden ministerineuvosto perustettiin vuonna 1971. Ministerineuvostolle luotiin vuonna 1972 sihteeristötoiminnot, ja Pohjoismaiden hallitukset virallistivat sihteeristön seuraavana vuonna.

Ministerineuvoston sihteeristö oli aluksi jaettu kahteen yksikköön, joista toinen sijaitsi Kööpenhaminan Snaregadella lähellä Christiansborgin linnaa, jossa Tanskan kansankäräjät kokoontuu. Tässä sihteeristössä käsiteltiin kulttuuri-, tutkimus- ja koulutusasioita. Kaikista muista yhteistyöalueista vastasi Oslon Skt. Olavsgatella toiminut toinen sihteeristö.

Molemmilla sihteeristöillä oli oma pääsihteeri. Vuosien varrella järjestely osoittautui kuitenkin raskaaksi ja kalliiksi, joten vuonna 1986 toimistot yhdistettiin, ja ne muuttivat Kööpenhaminaan osoitteeseen Store Strandstræde 18. Uuden sihteeristön pääsihteeriksi valittiin Fridtjov Clemet.

Heinäkuussa 2010 Kööpenhaminan-sihteeristö muutti osoitteeseen Ved Stranden 18. Samassa osoitteessa sijaitsevat myös Pohjoismaiden neuvoston ja Pohjoismaisen kulttuurirahaston sihteeristöt.