V roce 1780 se začalo se stavbou josefovské pevnosti. V téže době bylo faráři zapovězeno, aby nechával pohřbívat zemřelé na hřbitově u kostela sv. Jiljí. Jeho náhradou se stala místa při kapli sv. Huberta, kterou roku 1690 založil hrabě Špork. Naopak vojáci a lidé ze stavení u rasošského lesa a na místě pozdějších důstojnických sadů byli pochováváni v místech dnešního pevnostního hřbitova, kde byl prvním hrobníkem jistý Khörner. V roce 1788 došlo k úpravě hřbitova a obydlí pro hrobníka čp. 39, u něhož byla o 2 roky později vykopána nová studna. V té době se zde pohřbívali již vojáci společně s místními měšťany a jejich rodinami.
K nim postupně přibývali další. Mezi prvními z nich bylo 1 148 francouzských zajatců, jež se dostali do Josefova po bitvě u Lipska roku 1813 a zemřeli zde na svá zranění, útrapy nebo nemoci. Josef Duška ve svých "Pamětech c. k. pevnosti a královského svobodného města Josefova, se zřetelem k dějinám vlasti a vojenství": "Však takového obveselení bylo jim chuďasům v největší míře zapotřebí; neboť nemoci tou měrou se mezi nimi rozmohly, že od 29. prosince 1813. až do 20. června příštího roku odvezeno jich 1148 mužův na zdejší hřbitov vojenský, kdež kladeni z počátku, když nejhůře bylo a zima překrutá panovala, prostě na zem do kouta, k zadní západní straně hřbitova, až jich bylo značné množství pohromadě, potom po 2-3 dnech vykopány šachty a mrtvoly do nich vmetány. I stalo se jednoho dne po novém roce, že někteří obyvatelé blízkých Rasošek jdouce po své práci za časného rána do Josefova zaslechli ze hřbitova upěnlivé volání. Když jdouce blíže nahlíželi přes dřevěný plot do vnitra, uzřeli, že jeden Francouz z kupy se hrabe; neboť nebyl úplně mrtev. A protož dostavše se ti dobří lidé s hrobníkem k němu celého zkřehlého dovedli do chalupy hrobníkovy a potom do pevnosti; ale přece zemřel druhého dne na dobro." V roce 1815 byl postaven kolem hřbitova nový zděný plot a domek pro hrobníka. Roku 1831 byl zřízen pomník zemřelému generálmajoru Johannovi baronu Schmelzern von Wildmannsegg a o 6 let později zde byl pohřben první kněz - posádkový kaplan (de facto pevnostní farář) P. Thomas Reingruber. V roce 1843 došlo ke vztyčení pomníku trojici důstojníků z pěšího pluku Rainerova, jež zahynuli pod kopcem za Jaroměřskou bránou, když vypadli z vozu se splašeným spřežením. O 6 let později bylo rozhodnuto, že vojenský hřbitov zůstane společným.
Roku 1853 byl zřízen pomník příslušníkům pěšího pluku č. 21, kteří bojovali v letech 1848-1849 v Itálii a Uhrách, aby potlačili tamní revoluční hnutí. Celkem se do Josefova nevrátilo 11 důstojníků a 183 vojáků. Neznámé množství vojáků tu bylo pochováno rovněž po prusko-rakouské válce roku 1866. Vzpomínkou na to je zejména šestice důstojnických pomníků. Zemřelí v uzavřené pevnosti byli tehdy pochováni v předhradí Novoměstské brány v rohu fortifikačního pozemku mezi novopleskou a lejšovskou cestou. Jednalo se o 7 mužů - nadporučíka 25. mysliveckého praporu Karla Neumeiera, šikovatele 61. pluku Jiřího Demetera, Ondřeje Schönbauera od 4. kyrysnického pluku, Františka Delapria od 31. pluku, Dominika Pollatiho od 38., Josefa Sommera od 35. a vojína dragounského pruského pluku č. 1. Ti byli přeneseni na jaře 1867 na vojenský hřbitov, kde jim byl 30. dubna 1871 zřízen pomník. V roce 1875 zde byl pohřben první josefovský purkmistr Josef Traxler a 20. října 1877 byl posvěcen nově postavený hlavní hřbitovní kříž, jenž nahradil dosavadní černě natřený dřevěný krucifix, který byl již chatrný a hrozil pádem. Postaven byl díky místnímu spolku "Omladina", jenž za něj zaplatil 408 zlatých a 30 krejcarů.
V roce 1888 došlo sice ke zrušení pevnosti, ale pohřebiště nadále sloužilo též místní posádce. Roku 1899 zde byl pohřben poslední veřejně popravený voják, jímž byl vojín pěšího pluku č. 74 Rudolf Mlejnek, který 13. června 1898 zabil svého kamaráda, vojína Antonína Václavíka. Popraven byl 23. října 1899. Velký boom hřbitova nastal v období 1. světové války, neboť v Josefově fungoval velký internační tábor, v němž zemřela řada zajatců z Ruska, Itálie či Srbska. Roku 1916 byl na památku obětí války vztyčen betonový pomník od ruského zajatce N. A. Suškina, který byl zřízen ze sbírky ruských zajatců a jeho povolení schválila rakouská vláda. V roce 1918 bylo pohřebiště zvětšeno, a to na jeho západní straně. O 10 let později vznikl pomník nad hrobem spisovatele Josefa Dušky. V letech 1929-1934 bylo osázeno okrasnými keři a koniferami. 5. srpna 1932 byl na zeď starého vojenského hřbitova umístěn měděný turecký epitaf, informující o tom, že zde bylo pohřbeno 7 tureckých vojáků z 1. balkánské války (1912-1913), kteří byli 2.-5. února 1959 exhumováni a převezeni do společného hrobu do Pardubic. Roku 1937 byl obnoven Klubem Josefováků hlavní hřbitovní kříž. V roce 1941 došlo ke zřízení pomníku padlých příslušníků ukrajinské osvobozenecké armády a po osvobození od německých okupantů vznikl na hřbitově symbolický hrob obětí nacismu. 11. listopadu 1951 byl slavnostně odhalen pomník padlým rudoarmějcům, který byl vybudován nákladem josefovské odbočky Svazu československo-sovětského přátelství. 6. března 1964 bylo pohřebiště zapsáno do státního seznamu kulturních památek (viz
https://pamatkovykatalog.cz/pevnostni-hrbitov-12860062). Od té doby býval centrem různých oslav, spojených zejména se SSSR a spřátelenými státy z Varšavské smlouvy.
Po sametové revoluci došlo k zásadnímu obratu. Objevilo se totiž mnohem více nenechavců, kteří se snažili odcizit vše, co "není přivařeno nebo zabetonováno". V roce 1994 zmizel dokonce bronzový zvon a v srpnu 1998 kamenný náhrobek. Mnoho oprav však bylo provedeno až v posledních dekádách. V roce 1997 byla dokončena obnova hřbitova, která byla zahájena roku 1994 zrestaurováním Suškinova pomníku (město Jaroměř a Klub přátel Josefova). 6. září 1998 byl posvěcen nový zvon, jenž nechal Klub přátel Josefova odlít pro zdejší zvoničku. V letech 1994-1998 bylo na obnovu hřbitova použito z městského rozpočtu 448 372,50 Kč. Roku 2000 byla slavnostně odhalena pamětní deska zemřelým italským zajatcům a o 4 roky později jejich francouzským kolegům. 30. října 2001 došlo k exhumaci 18 německých vojáků ze 2. světové války, z nichž nejznámějším je svobodník Josef Seidlinger, jenž byl utlučen a ukopán jinými německými vojáky 6. května 1945. V roce 2012 byla část hřbitova upravena nákladem ruského státu, kdy zanikly původní rovy. Různých oprav, úprav a restauračních prací si však zažil hřbitov mnohem více, že by na jejich výčet nestačila ani tato stať. Na závěr je ještě třeba dodat, že kdo se chce dozvědět o tomto pohřebišti více, může nalistovat publikaci "Pevnostní hřbitov v Josefově", kterou roku 2002 vydal Václav Novák.