Novodevičiaus Bogorodice-Smolensko vienuolyną 1524 m. įkūrė didysis kunigaikštis Vasilijus III Smolensko sugrįžimui iš Lietuvos atminti. Iš pradžių vienuolyno sienos ir bokštai buvo mediniai, o XVI amžiaus pabaigoje iškilo akmeninės sienos su bokštais. Valdant carui Aleksejui Michailovičiui, vienuolynas virto karališka piligrimine kelione. Valdant princesei Sofijai Aleksejevnai buvo pastatyta varpinė, naujos bažnyčios, valgykla, gyvenamosios patalpos princesėms Marijai ir Kotrynai, Sofijos seserims. Maskvos baroko stiliaus architektūrinį vienuolyno ansamblį (išskyrus senąją katedrą ir sienas) saugo UNESCO.
Novodevičiaus vienuolynas kurį laiką buvo moterų karališkųjų asmenų įkalinimo vieta. Taigi, Petrui I atėjus į valdžią, princesė Sofija buvo įkalinta vienuolyne ir 1698 m. buvo tonzuota Siuzanos vardu. Valdant Petrui II, iš Suzdalio buvo perkelta pirmoji Petro I žmona Evdokia Lopukhina.
Po 1771 m. dekreto, draudžiančio laidoti miestuose, vienuolyno teritorijoje iškilo kilmingas nekropolis. Iki XX amžiaus pradžios vietos palaidojimams praktiškai nebeliko, o miesto valdžia skyrė sklypą už pietinės vienuolyno sienos po Novodevičiaus kapinėmis.
Kai vienuolyną užėmė Napoleono kariai, jame buvo įrengta baterija, traukimosi metu prancūzai padegė vienuolyną, tačiau vienuolės spėjo užgesinti ugnį. 1922 metais vienuolynas buvo uždarytas, 1926 metais paverstas Istorinės buities ir dailės muziejumi. 1994 m. vienuolynas vėl pradėjo veikti, dabar yra bendras Rusijos stačiatikių bažnyčios ir Valstybinio istorijos muziejaus jurisdikcijoje. Tai vienintelis vienuolynas Maskvoje, pavaldus ne tiesiogiai patriarchui, o Krutitskio ir Kolomnos metropolitui.