Cmentarz został założony w drugiej połowie XIX wieku przez wałecką parafię pw. św. Mikołaja. Pierwotnie zajmował około 60 arów, leżąc wówczas poza granicami zabudowań miejskich. Miał wówczas kształt prostokąta i regularny podział na kwatery. Aleje lipowe dzieliły wówczas cmentarz na cztery równe części. Najstarszy zachowany obiekt pochodzi właśnie z tego okresu – jest to kapliczka zwieńczona kompozycją figuralną Ukrzyżowania Pańskiego, postawiona w 1887 roku.
Pod koniec XIX wieku cmentarz został powiększony w kierunku północno-zachodnim i południowym i ogrodzony. Przyjął wówczas formę trapezu z prostokątnym występem od strony południowej. Po tej zmianie wymurowano od strony ulicy ceglane ogrodzenie z ciekawą architektonicznie bramą w stylu neogotyckim. Ozdobna w architektoniczne detale brama składa się z pięciu segmentów: Najwyższy, środkowy, stanowi portal bramy wjazdowej, po obu bokach znajdują się ostrołukowe portale bram wejściowych z tympanonami wypełnionymi rzeźbami. Najniższe boczne segmenty wykonane są w formie muru symetrycznie ozdobionego płaskimi niszami wgłębnymi, zamkniętymi od góry półkoliście, tworzącymi pozorne triforium. Oba segmenty zwieńczone są kolumnadą arkadową przykrytą dwuspadzistym daszkiem. Przypory rozgraniczające kolejne segmenty zwieńczone są prostymi pinaklami. W ostrołukowym portalu bramy wjazdowej umieszczono medalion z wyobrażeniem głowy Chrystusa.
Cmentarz zachował regularne rozplanowanie i rzędowe usytuowanie nagrobków. Widoczna jest zachowana ciągłość pochówków na kwaterach od 1913 roku do 1963 roku, kiedy to nastąpiło zamknięcie cmentarza. Nagrobki z wcześniejszego okresu zachowały się pojedynczo. Warto zwrócić uwagę na nagrobek Antoniego i Marii Łowińskich z 1898 roku, wykonany z czarnego, polerowanego kamienia na cokole z drapowanego piaskowca. Profesor Antoni Łowiński był ostatnim polskim dyrektorem wałeckiego gimnazjum (funkcję tę pełnił w latach 1866 – 1890). Prowadził lekcje łaciny i greki oraz języka polskiego w trzech najwyższych klasach dla uczniów polskich i tych spośród uczniów niemieckich, którzy chcieli uczyć się tego języka. Dzięki jego dyskretnej pomocy mogła się w Wałczu rozwijać tajna uczniowska organizacja o charakterze filomackim „Ul”. Mimo trudnych warunków politycznych przez 24 lata utrzymał się będąc Polakiem na stanowisku dyrektora gimnazjum. Zmarł w Wałczu 27 marca 1898 roku. Przy jego grobie zbierali się uczniowie filomaci by przyjmować przysięgi na wierność Polsce, składane przez nowo wstępujących do organizacji Ul. W domu państwa Łowińskich mówiło się tylko po polsku. Przewidując sprzeciw władz pruskich, Antoni Łowiński zastrzegł w swoim testamencie by na jego nagrobku umieszczono napisy w języku polskim lub ostatecznie w języku łacińskim, w przypadku gdyby to było niemożliwe, prosił o pozostawienie nagrobka tylko z napisem R.I. P. (requiescat in pace - niech spoczywa w pokoju ) do czasu, kiedy możliwe będzie wykonanie napisu po polsku. Po długotrwałych procesach rodzina uzyskała w sądzie wyrok pozwalający na umieszczenie napisu języku łacińskim. Po dojściu Hitlera do władzy, chciano zniszczyć ten nagrobek, rodzinie udało się go ochronić, jednak został on przez Niemców odwrócony tyłem do alei głównej.
Oprócz tego szczególnego grobu są jeszcze nagrobki ciekawe ze względu na ich wygląd: np. w formie złamanej kolumny jońskiej, czy też personifikacja płaczki opartej na złamanej kolumnie doryckiej.
Starodrzew cmentarza tworzą gatunki drzew liściastych, głównie lipy, jesiony, graby i klony z domieszką drzew iglastych: świerków i żywotników.