La ville est située sur la rive droite du Danube, entre les affluents de la Melk et de la Pielach. La vieille ville est surplombée par l'abbaye de Melk en haut d'une falaise.
Le lieu de Medilica fut mentionné pour la première fois en 831 ; à l'époque carolingien sous le règne de Louis le Pieux, les domaines appartenaient au diocèse de Passau en Bavière. Selon l'historien allemand Georg Heinrich Pertz, un chevalier normand nommé Ansgot ouvre à Melk un hospice pour les pauvres et les pèlerins vers le milieu du XIe siècle.
Les premiers moines à arriver furent les frères de l'abbaye de Lambach. Depuis, les bénédictins vivent et travaillent de façon ininterrompue à Melk. L'école monastique se développe à partir du XIIe siècle, ainsi que la grande bibliothèque abbatiale. Dans le roman d'Umberto EcoLe Nom de la rose, le narrateur (le novice bénédictin Adso) est originaire de l'abbaye de Melk, et c'est de là qu'il rédige son récit, de nombreuses années après le déroulement des faits.
Le village au-dessous du monastère obtint le droit de tenir marché en 1227. En 1898, Melk est élevé au rang de ville.
Du jusqu'à l'évacuation du se trouvait à Melk, sur le site de la caserne Freiherr-von-Birago, un camp de concentration, extension du camp de Mauthausen, exploité par le groupe industriel Steyr Daimler Puch pour le projet « Quartz »[2],[3]. Dans celui-ci, 4 896 personnes perdirent la vie pendant son année d'existence[4]. Il n'en reste aujourd'hui que le crématorium, en tant que mémorial.