Территория нынешнего кладбища Мелатен известна с 1180 года. В те времена на этом участке, являвшемся тогда достаточно отдалённым предместьем средневекового Кёльна, находился лепрозорий — место, где «изолировали» от внешнего мира прокаженных. От этого заведения, первоначально именовавшегося также Maladen (предположительно о французского слова malade = «больной»), и происходит название Melaten, которое позднее, помимо собственно лепрозория, распространилось и на весь большой пустырь к западу от городских укреплений, где сегодня находится некрополь. С XVI по XVIII века в этом месте процветало питейное заведение, бывшее излюбленным местом посещения для малоимущих горожан. Одновременно пустырь был облюбован и как место для публичных казней. Так, в XVI и XVII веках здесь было сожжено на костре значительное количество подозревавшихся в колдовстве и ереси горожан (в том числе признанный позднее мучеником за дело Реформации Адольф Кларенбах в 1529 году, а также Катарина Хенот, известная жертва охоты на ведьм, в 1627 году). Впрочем, и после упразднения инквизиции Мелатен вплоть до конца XVIII века продолжал служить местом исполнения смертных приговоров. При этом трупы казнённых обычно там же и закапывали в землю.
В период занятия Кёльна французскими войсками (1794 - 1814 гг.) одним из многочисленных нововведений в городской жизни стал изданный Наполеоном I в 1804 году указ, запрещавший из соображений общественной гигиены хоронить умерших горожан на церковных погостах в черте города, как это было до этого принято среди знатных граждан, а также лишавший католическую церковь права проводить погребения и возлагавший эту работу на муниципальные власти. Это породило необходимость устройства вблизи городских границ крупного муниципального кладбища, и вскоре в качестве участка для этого кладбища был выбран пустырь вблизи бывшего лепрозория. 
В переустройстве Мелатена под кладбище ключевую роль играл бывший ректор Кёльнского университета Фердинанд Франц Вальраф, предложивший обустройство некрополя наподобие основанного несколькими годами ранее парижского кладбища Пер-Лашез, со строго геометрической сетью аллей и дорожек, а также с густым насаждением деревьев по образцу пейзажного парка. К 1810 году была возведена кладбищенская стена с несколькими сохранившимися и поныне воротами, а также отреставрирована построенная в XV веке часовня лепрозория, включённая в общий ансамбль некрополя. 29 июня 1810 года состоялось открытие нового кладбища.
Несмотря на муниципальный статус Мелатена, в первые годы после его основания там разрешалось хоронить умерших только католикам, в то время как для протестантов (до 1829 года) и иудеев(до 1892 года) продолжали существовать собственные конфессиональные кладбища. Таким образом, первоначально количество захоронений на Мелатене было сравнительно невелико, и только в 1833 году территория кладбища впервые была расширена. В период индустриализации во второй половине XIX века население Кёльна стремительно росло, что сделало необходимым дальнейшие расширения кладбища 1850, 1868, 1875 годах, а также основание нескольких новых муниципальных кладбищ в самом начале XX века. 
В этот же период на Мелатене было возведено несколько новых сооружений, в том числе поминальный дом (1881), здание кладбищенской конторы (1889), две сторожки (1901/02), а также общественная уборная (1896). Все эти здания, равно как и ряд старых надгробных памятников, сильно пострадали в 1945 году при бомбардировках Кёльна во врем Второй мировой войны, некоторые из них впоследствии были восстановлены, а в дополнение к старому поминальному залу 1957 году был построен новый. Средневековая часовня лепрозория также была при бомбёжках разрушена и в 1952 году воссоздана в несколько упрощённой форме.
«Смерть с косой» — один из известнейших памятников на Мелатене
На Мелатене сохранилось большое количество примечательных или оригинальных надгробных скульптур, многие из которых были изготовлены в XIX веке при участии известных скульпторов и архитекторов и представляют собой историческую ценность. Особенно много таких памятников находится на «Миллионной аллее», как часто называют дорогу, пересекающую некрополь с востока на запад. Поскольку в XIX веке основная часть захоронений городской знати осуществлялась вдоль или вблизи этой аллеи, именно там находится ряд надгробий известных семей фабрикантов, банкиров, издателей и учёных. Так как в XIX веке на Мелатене хоронили в основном католиков, здесь можно найти много памятников в неоготическом стиле, перекликающихся с основной достопримечательностью города — Кёльнским собором.
Ярко представлены и другие стили той эпохи, например неоренессанс, неоклассицизм и модерн. В 1980-х годах городскими властями Кёльна была разработана система так называемого шефства над историческими надгробиями, при которой любой желающий может отреставрировать старый памятник за свой счёт, получив взамен пожизненное право захоронения в могиле себя или близких. Эта система, практикующаяся сегодня не только в Кёльне, но и во многих других городах Германии, позволила сохранить на Мелатене значительное количество ценных памятников, которым до этого грозило разрушение.
С XX века на Мелатене стали появляться и захоронения нехристианских конфессий, и сегодня там существует, в частности, значительное количество мусульманских могил, а также отдельный еврейский участок, отгороженный от остального кладбища. Имеются и братские захоронения жертв Первой и Второй мировых войн.
так и экзотические для Европы индийские кольчатые попугаи, стаи которых с 1960-х годов, когда несколько особей были выпущены на свободу и сумели приспособиться к здешним климатическим условиям и произвести потомство, можно встретить практически в любом парке в Кёльне и окрестностях. Кроме того, на Мелатене обитают летучие мыши, белки, одичавшие кошки и даже лисы.
