Muzej savremene umetnosti osnovan je 20. oktobra 1965. godine, kada je zgrada na Ušću svečano otvorena za javnost. Deset godina ranije, 1955. godine imenovan je Odbor Moderne galerije, koji je bio zadužen da pripremi teren za osnivanje Moderne galerije 1958. godine, institucije koja je započela prikupljanje i stručnu obradu umetničkih dela nastalih od početka 20. veka. Za upravnika Moderne galerije je imenovan Miodrag B. Protić, slikar, kritičar i teoretičar umetnosti. Zahvljujući Protićevom zalaganju, entuzijazmom i posvećenošću ideji osnivanja Muzeja savremene umetnosti, već 1959. godine je raspisan konkurs za arhitektonsko rešenje zgrade Muzeja. Izabrano je rešenje arhitekata Ivana Antića i Ivanke Raspopović i gradnja je započeta 1960. godine.
Muzej savremene umetnosti u Beogradu nije bio prva institucija posvećena prikupljanju i prezentovanju moderne umetnosti u Jugoslaviji (prethodile su joj Moderna galerija u Ljubljani, Galerija likovnih umjetosti u Rijeci, Gradska galerija suvremenih umjetosti u Zagrebu), ali je bila jedinstvena po jugoslovenskoj orijentaciji. Insistiranje na jedinstvenom prikazu umetnosti nastale na čitavoj teritoriji tadašnje republike nailazilo je na otpore još pre osnivanja Muzeja. U knjizi „Nojeva barka“, Protić kaže: „Jer zbog jedinstvenog prostora u kome se razvojni proces odvijao u oblasti slike, univerzalnog medija, granice nije uvek bilo moguće povući...“ Prigovori koji su se javili zamerali su da se tim konceptom smanjuje prostor za predstavljanje srpske umetnosti i da slične ustanove u Ljubljani i Zagrebu ne prestavljaju dovoljno radove srpskih umetnika. Ipak, Protić je odbranio ovaj koncept argumentom da se srpska umetnost bez jugoslovenske ne može prikazati u evropskom kontekstu.
Sledeća prepreka bile su osude na račun izgleda zgrade, i uopšte potrebe da se gradi nova zgrada. Vlast je nudila napuštena zdanja da se prilagode i adaptiraju za muzej, što je bilo neprihvatljivo, ali ne tako lako odbarnjivo. Kao kompromis, muzej je dobio ne tako atraktivnu lokaciju; zemljište van gradskog jezgra, na novobeogradskoj strani reke Save.
Izgradnja zgrade Muzeja savremene umetnosti je trajala od 1960. do 1965. godine, u vreme hladnog rata, Titovog govora protiv apstraktne umetnosti, a pred studentske nemire 1968. godine. Izgled zdanja je bio često na meti kritika iz političkih krugova. U nekoliko navrata je pokušavano da se povuku sredstva za izgradnju i opremanje Muzeja, pa je tako 1963. godine Protić bio primoran da prekine studijski boravak u Americi i da se ranije vrati kako bi odbranio troškove za parket u izložbenim salama i kamen za fasadu. Prema Protićevom svedočenju, predsednik Izvršnog veća Skupštine Socijalističke Republike Srbije na sednici vlade je tražio da se ti troškovi priznaju rekavši: „Bolje da platimo i to, nego da sutra mi budemo krivi zbog očigledno ružnog objekta“.
Muzej je otvoren 1965. godine postavkom jugoslovenske umetnosti 20. veka i kroz svoj rad je nastavio da prikuplja, istražuje, prestavlja, dokumetnuje umetnost jugoslovenskog prostora. Zahvaljujući naporima i borbama Miodraga B. Protića, jednog od najrevnosnijih interpretatora i učesnika progresivne koncepcije umetnosti, Beograd je dobio Muzej savremene umetnosti. Protićeve ideje su čvrsto utkane u politiku Muzeja, kao što su orijentacija ka jugoslovenstvu i socijalistički progresivizam. Američki Njuzvik je 1966. godine za Muzej savremene umetnosti napisao da „stoji kao ultramoderni spomenik umetničkoj slobodi. Najprovokativnija i najoriginalnija građevina koja je ikada podignuta u jednom socijalističkom društvu… Po svom duhu, on predstavlja, kako je jedan zapadni posmatrač rekao, moderni i vedri nadgrobni spomenik socijalističkom realizmu”.
Posle raspada Jugoslavije Muzej savremene umetnosti je nastavio da čuva, ali i nabavlja dela savremenih umetnika iz bivših jugoslovenskih republika kao i drugih država u regionu što doprinosi da Muzej sve više postaje orjentisan ka regionalnom i internacionalnom umetničkom nasleđu što proširuje njegovu exjugoslovensku orijentaciju.