W kwietniu 1805 roku parafia św. Wojciecha zakupiła teren pod przyszły cmentarz na terenie wsi Bonin. W 1828 roku zapadła decyzja o budowie twierdzy na Wzgórzu Winiarskim. Teren pod cmentarz został zajęty przez Komisję Fortyfikacyjną. Prace przy budowie twierdzy objęły również wzgórze św. Wojciecha. Wzgórze zostało częściowo niwelowane, co spowodowało znaczne okrojenie cmentarza przykościelnego. W listopadzie 1833 została podpisana ugoda pomiędzy Komisją Fortyfikacyjną a parafią Św. Wojciecha. W ramach rekompensaty, parafii wydzielono prostokątną działkę na zboczu Wzgórza Winiarskiego, w pobliżu Cytadeli. Działka była długa na 39 prętów i 2 stopy pruskie, oraz szeroka na 19 prętów i 9 stóp pruskich, co dawało powierzchnię 4 mórg i 41 prętów kwadratowych; północno-zachodni narożnik prostokąta został ścięty, aby nie kolidować z forteczną drogą krytą, przebiegającą nad cmentarzem – wzdłuż fosy. Na wschód od cmentarza został przewidziany teren pod cmentarz garnizonowy. Cmentarz w krótkim czasie zaczął pełnić swoje funkcje. Co do początkowego okresu działalności cmentarza brak jakichkolwiek źródeł.