Демо містило 32 хвилини ностальгічною музики, яку можна було визначити як містично-симфонічний дум-дез з великою кількістю клавішних. Ця робота була тепло зустрінута слухачами і андеграундної польською пресою.
До осені 1993-го в команді з'явилися нові учасники - гітарист Артур Олешкевич і клавішниця Кася Рачвалік. У липні 1994 року група виступила на найбільшому польському фестивалі андеграундної музики "S trash ydlo 94".
Після цього "Cemetery of Scream" знов опинилися в студії "Gamma" і записали свій перший альбом "Melancholy". До сесій були залучені також друзі музикантів - Петро Лабузек (співпродюсер і звукоінженер) грав на клавішних, Магда Джагларж і Пауліна Пивоварчик виконували вокальні партії, а де-не-де звучали сольні гітарні партії Павла Горальчіка. Платівка занурювала слухача в глибини людських почуттів, тексти, чудово поєднуються з музикою, оповідали про печалі, радості, краси, страху і болю. На пісню "Anxiety" був знятий відеокліп, випущений в компіляції від "Nuclear Blast Records" під назвою "Beauty in Darkness".
Цікаво відзначити, що в цей збірник входили творіння таких монстрів жанру як "Lacrimosa", "Tiamat", "Love like blood" і "Therion". На цьому етапі про "Cemetery of Scream" заговорили не лише в Польщі, але і за кордоном.
Голландський журнал "Aardschok" проголосив "Melancholy" альбомом місяця, а німецький "Metal Hammer" присвятив диску хвалебну статтю. Незабаром Артура Олешкевича змінив відомий на польській металевої сцені гітарист Павло Горальчік. З його появою "Cemetery of Scream" придбали ще більший успіх за кордоном. Журнал "Rock Hard" написав, що все що робить ця польська група, вищої якості. Цей відгук повністю відповідав дійсності, оскільки і музика і тексти насправді були хороші. За розповсюдження наступних платівок в Європі взявся німецький лейбл "Serenades Records".
Перед випуском чергового полноформатніка "Prelude to a Sentimental Journey" група випустила міні-альбом "Fin de Siecle". Настрій цього EP було навіяно останніми світовими політичними подіями, такими як війна в Югославії, чеченські події та іншими конфліктами. Музиканти "Cemetery of Scream" висловили свій протест всього цього поверненням до декадансу.