До сих пор умерших хоронили на специально отведенных участках на Повонзках и двух протестантских кладбищах — кальвинистском и лютеранском, где уже в 1798 году православная община приобрела землю. К 20-м годам XIX века на всех трех кладбищенских участках перестало хватать мест, к тому же небольшие протестантские приходы все более активно сопротивлялись православным погребениям, опасаясь — не без причины, — что вскоре их прихожане и вовсе лишатся возможности хоронить своих усопших.
По приказу Николая I от ноября 1834 года для православного кладбища выбрали территории, прилегающие к католическому костелу св. Лаврентия в районе Воля под Варшавой на месте прежнего редута № 56 — важного звена оборонительных укреплений польских повстанцев. Именно здесь во время ноябрьского восстания велись ожесточенные бои за Варшаву между поляками и войсками генерала-фельдмаршала Ивана Федоровича Паскевича. Именно здесь, у костела св. Лаврентия, пал геройской смертью генерал Юзеф Совинский, командующий обороной Воли. Вскоре после этих событий Вольский редут и руины костела стали местом паломничества польских патриотов, так что выбор именно этого участка был продиктован желанием властей противостоять мифу героической польской обороны. Использовался и религиозный аргумент: в успешном подавлении восстания надлежало видеть перст божий — русские войска прорвали оборону 6 сентября (25 августа по старому стилю), а на следующий день в России праздновали сретение Владимирской иконы Пресвятой Богородицы. В связи с этим костел св. Лаврентия, сильно пострадавший во время штурма, было решено восстановить, перевести в ведение православной церкви и окрестить церковью Чудотворной иконы Владимирской Богоматери.
Могила героя, или О пользе знания геральдики
С православным кладбищем связана легендарная история могилы Юзефа Совинского. Считалось, что героически погибший при обороне редута генерал похоронен вблизи костела св. Лаврентия. В 1842 году там, где предположительно находились его останки, погребли российского генерала Александра Муравьева. По мысли властей, это должно было положить конец патриотическим паломничествам к могиле героя, однако история приняла совершенно другой оборот. С течением времени о Муравьеве позабыли, а его надгробие стали воспринимать как памятник в честь Совинского. Подобный казус объяснялся ошибочным прочтением изображенного на надгробии герба покойного российского генерала. В сотую годовщину ноябрьского восстания, уже в независимой Польше, решили провести эксгумацию, чтобы выяснить, чей прах в действительности покоится на этом месте. Оказалось, что в могиле находятся только останки Муравьева. Их положили в новый гроб и перезахоронили с соблюдением всего соответствующего церемониала.
Подготовительные работы и первые захоронения: из редута — некрополь
Землю под строительство кладбища приобрели у семьи Порай-Бернацких, владельцев большей части территории Воли. Первоначальный участок ограничивался земляным валом, оставшимся от прежних окопов. Сегодня сохранившиеся фрагменты вала оказались в центре разросшегося некрополя. Деньги на строительство кладбища были выделены из казны Царства Польского, а также изъяты из фонда, собранного польскими гражданами на установление памятника князю Юзефу Понятовскому. Заказ на памятник получил известный датский скульптор-классицист Бертель Торвальдсен. Статую доставили в Варшаву, но даже не успели распаковать — вместе с оставшимися в фонде деньгами ее тут же реквизировали царские власти. В конце концов, после различных пертурбаций, она оказалась в гомельской резиденции Паскевича, бывшего тогда наместником Николая I в Царстве Польском. Деньги же были потрачены на подготовку территории к размещению кладбища — проведение земляных и озеленительных работ поручили инженеру-поручику Филиппу Ивановичу Голикову. Голиков также разработал общий план кладбища, обозначил аллеи и участки, места посадки деревьев и расположение клумб, укрепил поврежденный в нескольких местах земляной вал.
Официальное открытие кладбища, сопровождаемое военным парадом, состоялось в августе 1841 года — в десятую годовщину подавления восстания. Тогда же освятили церковь Владимирской иконы Божией Матери, которая стала выполнять функцию кладбищенского храма. Однако первыми православными захоронениями на этом месте стали общие могилы российских военных — офицеров и солдат резервного кавалерийского корпуса, погибших еще при штурме Воли в 1831 году. Именно они дали начало вольскому некрополю (польских защитников редута похоронили за его стенами). Первое захоронение, уже не связанное со взятием Воли, датируется 1836 годом — 26 июня здесь был погребен варшавский военный губернатор генерал Никита Петрович Панкратьев, который, кстати, непосредственно руководил работами по обустройству некрополя. За пять дней до его похорон состоялось первое освящение кладбища. Лишь спустя три года, в 1839-м, строительство было завершено и кладбище передали в ведение церкви.