Kirkegården råder over et større kapel og har over 12.000 gravsteder. Blandt dem er også en del jødiske og muslimske gravsteder. De er indhegnet og har en separat indgang. Kapellet blev tegnet af Peter Jürgensen og blev opført i en karakteristisk slesvig-holstensk hjemstavnsstil (som modsvarer den danskestilartBedre Byggeskik). Kapellet kan rumme ca. 250 personer.
Navnet Fredshøj henviser til en tidligere grænsekonflikt mellem sognene Sankt Nikolaj og Sankt Marie (Vor Frue) i Indre By, som blev afsluttet i 1718.
De to andre kirkegårde i Flensborg er Den Gamle Kirkegård fra 1811 og Møllekirkegård fra 1872. De nye kirkegårde afløste de mindre kirkegårde ved bykirkerne.