Luostari perustettiin vuonna 1089, kun Itävallan markkuri Leopold II antoi yhden linnoistaan Lambachin luostarin benediktiinimunkkeihin. Luostarikoulu, Stiftsgymnasium Melk, perustettiin 1200-luvulla, ja luostarin kirjasto tuli pian tunnetuksi laajasta käsikirjoituskokoelmastaan. Luostarin scriptorium oli myös tärkeä käsikirjoitusten valmistuspaikka. Viidennellätoista vuosisadalla luostarista tuli Melkin uudistusliikkeen keskus, joka elvytti Itävallan ja Etelä-Saksan luostarielämää.
Tämän päivän barokkiluostari rakennettiin vuosina 1702-1736 Jakob Prandtauerin suunnitelmien mukaan. Erityisen huomionarvoisia ovat luostarikirkko, jossa on Johann Michael Rottmayrin freskoja, ja kirjasto, jossa on lukemattomia keskiaikaisia käsikirjoituksia, mukaan lukien kuuluisa musiikkikäsikirjoituskokoelma ja Paul Trogerin freskoja.
Melk onnistui maineensa ja akateemisen asemansa ansiosta välttymään keisari Joosef II:n aikana tapahtuneelta lakkauttamiselta, kun monet muut itävaltalaiset luostarit takavarikoitiin ja lakkautettiin vuosina 1780-1790. Luostari onnistui selviytymään muista sen olemassaoloon kohdistuneista uhkista Napoleonin sotien aikana ja myös vuoden 1938 Anschlussin jälkeisenä aikana, jolloin valtio takavarikoi koulun ja suuren osan luostarista.
Koulu palautettiin luostarille toisen maailmansodan jälkeen, ja se palvelee nykyään lähes 900:aa oppilasta kummastakin sukupuolesta.
Vuodesta 1625 lähtien luostari on ollut Itävallan kongregaatioon, nykyisin Benediktinusliiton jäsen.
Romaanissaan Ruusun nimi Umberto Eco nimesi yhden päähenkilöistä ”Melkin Adsoksi” kunnianosoituksena luostarille ja sen kuuluisalle kirjastolle.
Luostarissa opiskeli muun muassa 1800-luvun itävaltalainen draamakirjailija ja novellisti Friedrich Halm.
Melkin luostari on myös metaforinen huipentuma (”huippu löytöjen vuoristossa”) Patrick Leigh Fermorin omaelämäkerrallisessa kertomuksessa toisen maailmansodan aikaiseen Eurooppaan suuntautuneesta kävelymatkastaan teoksessa A Time of Gifts (Lahjojen aika), joka sisältää kuvauksen luostarista tuolloin.
Luostari on osa Wachaun kulttuurimaisemaa, joka on maailmanperintökohde.