Madonas novadpētniecības un mākslas muzeju nodibināja 1944.gada septembrī, kad Madonas apriņķa partijas komitejas 1.sekretāre Ieva Pliesmane atbalstīja Elzas Rudenājas (1911-1998) ideju par muzeja izveidošanu. Rudenāja pirms Otrā pasaules kara bija studējusi vēsturi Latvijas Universitātē un bija aizrāvusies ar arheoloģiju. Viņai bija arī muzeja darba pieredze.
Par Madonas muzeja pamatu kļuva Cesvaines skolas muzeja kolekcijas, kuras gan bija stipri izlaupītas kara laikā.  Enerģiskā un mērķtiecīgā Rudenāja aicināja vietējos iedzīvotājus un vietējās varas iestādes palīdzēt papildināt muzeja kolekcijas, un atsaucība bija ļoti liela.
1945. gadā Pliesmani atcēla no amata, it kā tādēļ, ka viņa pietiekami necīnoties ar kulakiem un citiem padomju varai nevēlamiem elementiem. Funkcionāri, kas nomainīja Pliesmani, nebija īpaši ieinteresēti muzeja pastāvēšanā. Līdz pat sešdesmito gadu vidum muzejam visai regulāri nācās pārciest dažāda veida vietējo funkcionāru, kā valsts drošības orgānu uzbrukumus, daļēji tādēļ, ka Rudenāja bija pieņēmusi darbā vairākus cilvēkus, ko bija represējusi padomju vara (Vladislavs Urtāns bija viens no viņiem). Tomēr muzejs izdzīvoja un izveidojās par vienu no labākajiem Latvijas novadpētniecības muzejiem. Lai gan Rudenāja nebija kompartijas biedre (ar dažādām atrunām viņa vairākkārt bija noraidījusi priekšlikumus iestāties), viņas sociālās prasmes, draudzīgās attiecības ar Kultūras ministrijas ierēdņiem un it sevišķi ar daudziem pazīstamiem kultūras darbiniekiem (piemēram, Mirdzu Ķempi) palīdzēja noturēties amatā un uzturēt muzeja reputāciju. Kopš piecdesmito gadu vidus Madonas rajonā tika izveidoti vairāki rakstnieku un citu kultūras darbinieku muzeji, un tie kļuva par Madonas muzeja filiālēm.  Madonas muzejs izveidojās par reģionālu novadpētniecības muzeju centru; tā filiāle bija arī Alūksnes novadpētniecības muzejs.
Kopš sešdesmito gadu vidus vietējo funkcionāru attieksme pret Madonas muzeju kļuva labvēlīgāka, un tie vairāk sāka palīdzēt muzejam, it sevišķi pēc tam, kad 1970. gadā par rajona partijas komitejas 1. sekretāru kļuva Leo Bērziņš. Sešdesmitajos gados daudzi gleznotāji, kas bija saistīti ar Madonas novadu, sāka dāvināt gleznas muzejam un pamazām tika izveidota vērā ņemama tēlotājas mākslas darbu kolekcija. 1984. gadā uzbūvēja jaunu izstāžu zāli, dodot iespēju parādīt muzeja kolekcijas. 1990. gadā Rudenāja nopietni saslima, un par direktori kļuva muzeja darbiniece Līvija Zepa. 1997. gadā Elzas Rudenājas pūliņi kultūras mantojuma saglabāšanā tika novērtēti, apbalvojot viņu ar Triju Zvaigžņu ordeni.
Padomju laikā Madonas muzejs atradās Kultūras ministrijas pārziņā un to finansēja valsts. Deviņdesmitajos gados Madonas novadpētniecības un mākslas muzejs, tāpat kā citi novadpētniecības muzeji, nonāca pašvaldību pakļautībā. Muzejs ir iesaistīts dažāda veida aktivitātēs un projektos.
E. Rudenāja dibināja muzeju ar skaidru mērķi - saglabāt Madonas reģiona vietējo un nacionālo identitāti, un šis mērķis saglabāja nozīmi turpmākajās desmitgadēs, neskatoties uz to, ka padomju varas iestādes centās izmantot muzeja darbību saviem ideoloģiskajiem mērķiem.