Museet har til huse i Domkirkeplads 5, som er bygget som rådhus i 1857, længe før kvinderne fik stemmeret.

Bygningerne var politistation fra 1941 til 1984, hvorefter museet flyttede ind og viste sin første udstilling for publikum i efteråret 1984. Museet blev statsanerkendt fra 1991. I 1992-94 renoverede Århus Kommune bygningerne fra kælder til kvist for i alt 10 mio.

Mathilde Fibigers Have blev efterfølgende anlagt som en offentlig plads beliggende ved museets bygning. Her arrangeres fra tid til anden events.

Kvindemuseet i Danmark startede som en græsrodsbevægelse, en museumsforening, som havde det dobbelte formål at opbygge et kvindemuseum og skabe arbejdspladser for kvinder. Museumsforeningen blev stiftet ved en generalforsamling den 31. oktober 1982. I festugen 1984 viste museet sin første større udstilling: Giv plads for liv, om tjenestepigeliv, moderskab og ungpigedrømme. Herefter har museet vist 4-6 nye udstillinger årligt og opbygget en bred og alsidig samling og dokumentation af kvinders historie.