1779 so ob podružnični cerkvi sv. Krištofa uredili staro ljubljansko pokopališče. Do sredine 19. stoletja so ga večkrat povečali. Čeprav se je nevarno bližalo mestu in naseljem, je deželna vlada 1871 izdala dovoljenje za vnovično širitev.
Po potresih 1895 in 1897 so začeli pripravljati vse potrebno za graditev novega pokopališča, saj so bile na pokopališču Sv. Krištof higienske razmere nevzdržne. Prvi pogreb na novem pokopališču je bil 2. maja 1906, o čemer poročajo tudi tedanji časopisi.
Od 1906 novo pokopališče ob cerkvi sv. Križa je od začetka sprejemalo tudi pokojnike od sv. Krištofa. Vedno več je bilo prekopov. Leta 1925 niso smeli več pokopavati v grobnice na starem pokopališču. 1923 so na novo pokopališče prenesli tudi posmrtne ostanke Dragotina Ketteja in Josipa Murna. Ureditev groba slovenske moderne je sprožila vprašanje in zanimanje za grobove pomembnih mož, ki so bili na opuščenem pokopališču že precej načeti.
Po letu 1920 so mesto širili proti severu, število prebivalstva je raslo, pojavila se je potreba po ustanovitvi nove župnije.
1929 je bilo zato osnovano Društvo za ustanovitev župnije in zidavo cerkve sv. Cirila in Metoda, ki se je ukvarjalo tudi z načrti za dozidavo obstoječe cerkve sv. Krištofa. Marca 1929 je bila objavljena Plečnikova študija regulacije severnega dela Ljubljane, ki na nekdanjem pokopališču pri sv. Krištofu ni predvidevala zazidav, ampak pokopališče nedolžnih otrok oziroma park zaslužnih mož. Plečnik je pozneje namesto tega zasnoval prizidek k stari cerkvi. Plečnik je stare arkade iz leta 1865 v načrtu dopolnil s pravokotno postavljenimi novimi arkadami, vmesni prostor pa si je zamislil kot gaj. Med zahodnim delom pokopališča in cerkvijo je predvidel majhna ograjena pokopališča, ob zidu na desni strani grobnice, na levi pa nasade in grobove. Zgodovinsko in oblikovno pomembne spomenike je nameraval ohraniti na starih mestih, nekatere pa bi v skupinah postavili ob prizidek cerkve sv. Krištofa in k dohodu do bodočega Hrama slave.
Jeseni 1933 so začeli graditi prizidek na severni strani cerkve sv. Krištofa; Izkopane posmrtne ostanke z zazidanega pokopališkega prostora so prenesli v posebej pripravljeno grobnico v cerkvi, zanimivejše spomenike s tega dela pa so vzidali v zunanje stene prizidka.
1. julija 1934 je sledila posvetitev nove cerkve sv. Cirila in Metoda. Staro pokopališče se je praznilo zaradi nasipavanja trase nove Linhartove ceste. Jeseni leta 1934 je bila odrejena prepoved pokopavanja na evangeličanskem pokopališču, ki se je nahajalo na vzhodnem delu starega pokopališkega prostora. V prihodnje naj bi bil ta prostor delno zazidan, delno pa uporabljen za park slave.
1936 se je ljubljanska škofija odločila za gradnjo novega semenišča na opuščenem pokopališču, načrte zanj je napravil arhitekt Plečnik. V tem in naslednjem letu je pripravljalni odbor za ureditev grobov zaslužnih mož zaupal načrt za spominski park Jožetu Plečniku. Škof Gregorij Rožman je odstopil del opuščenega pokopališkega zemljišča mestni občini, zato se je odbor raje kot za sv. Križ odločil za prostor ob arkadah na vzhodnem delu starega pokopališča. Za finančno pomoč 250.000 dinarjev za popravilo zidu, arkad, spomenikov, za ureditev portala, čiščenje terena in vrtnarska dela, so se obrnili na bansko upravo. 1937 je vodenje del in nadzor pri urejanju spominskega parka po Plečnikovem načrtu prevzel arhitekt Ivo Spinčič. Najprej so podrli barake na Vilharjevi cesti, last železnic, da bi uredili vhod v park. Pri urejanju vhoda za stopnice, zidce in tlake so uporabili fragmente starih nagrobnikov, železna vhodna vrata so izdelali iz ograje nekega grobnega prostora, streho obnovljenih arkad pa pokrili s skriljem z nekdanje jahalnice.
Plečnik je želel posmrtne ostanke položiti v skupne grobnice pod arkadami, odbor pa je zahteval individualne pokope, v parku pa bi dobili mesto le nagrobniki zaslužnih mož. Prostorsko je bil gaj zaslužnih mož zamišljen kot del kompleksa, ki se je nadaljeval onkraj Robbove ulice z evangeličanskim pokopališčem. Vmes naj bi vodila na novo urejena Robbova ulica. Predvidena je bila tudi možnost širitve parka proti Vilharjevi cesti.
Za živo mejo iz cipres, ozelenitev in nasade je po načrtih arhitekta Spinčiča poskrbel upravitelj mestnih nasadov Anton Lap. Odprtje Navja 30. oktobra leta 1938 je z govorom obeležil tudi tedanji ljubljanski župan Juro Adlešič.
1952 je sledila nacionalizacija Baragovega semenišča, 1955 in 1956 pa je prišlo do razlastitve Pokopališkega sklada in župnišča. Že 1955 so pred Baragovim semeniščem začeli graditi halo A za Gospodarsko razstavišče. 1956 je bilo ukinjeno evangeličansko pokopališče, posmrtne ostanke pa so odtod prenesli na Žale. 1957 so podrli župnišče in cerkev sv. Cirila in Metoda – le-to so prenesli na Vodovodno cesto. V začetku 1958 je bila porušena cerkev sv. Krištofa.
Gospodarsko razstavišče in pomožna skladišča so se vse bolj širili, gaj zaslužnih mož pa je postajal vse bolj utesnjen in ga ni bilo več možno kakovostno vzdrževati. Plečnik je razmišljal o prenosu Navja na Žale.
V 60. letih 20. stoletja so skrb za Navje prevzeli dijaki bežigrajske gimnazije, občasno tudi učenci bližnjih osnovnih šol.
Med iskanjem novega prostora v 70. letih je Navje propadalo. V začetku leta 1978 se je zgodilo vandalsko divjanje, med katerim so v parku prevračali in razbijali spomenike. Marca 1978 so spomenike zopet postavili v izogib sramoti pred kongresom Zveze komunistov Slovenije.
1980 je bil izdelan načrt prestavitve nagrobnih spomenikov z Navja na področje zelenih površin ob vstopnem delu pokopališča Žale, vendar so temu nasprotovali kulturne ustanove, Društvo slovenskih pisateljev, Društvo za varstvo okolja Ljubljane, druga društva in posamezniki. Zato so 1981 sprejeli sklep o obnovitvi in trajnem vzdrževanju spominskega parka Navje na obstoječi lokaciji; ustanovljen je bil odbor za ureditev Navja in sklenjen dogovor o njegovih ureditvi in financiranju.
Ljubljanski regionalni zavod za varstvo naravne in kulturne dediščine je 1982 pripravil program obnove in vodil ter nadzoroval vsa restavratorska ter gradbeno-konstrukcijska dela. Sodelovalo je tudi podjetje JUB s finančno in materialno podporo.
Med 1982 in 1986 je potekala celostna obnova Navja: prenovili so arkade, uredili odtoke, sanirali zidove, tlake, električne instalacije. Potekala so konservatorska in restavratorska dela, zlatenje napisov, obnova vseh nagrobnikov zunaj arkad, sanirali so portal, ograjo, park so vrtnarsko preuredili. 1985. je Komite za družbene dejavnosti občine Ljubljana-Bežigrad izdal odločbo o začasni razglasitvi preurejenega Navja za kulturno-zgodovinski spomenik. 1987 je taka razglasitev dokončno obveljala. Skrbnik spomeniškega območja je postalo podjetje Slovenijales – DO Trgovina. O vsem tem dogajanju nam je veliko novic prineslo glasilo Zbor občanov.
Navje je le kratek čas ohranilo prenovljeno podobo. Ob veliki poselitvi okoliša v naslednjih letih in slabega nadzora je Navje postalo pribežališče nekulturnih posameznikov in izgrednikov: v Dnevniku, Delu in drugih časopisih so pisali, da se je tam popivalo in prirejalo piknike. Zaradi tega so 1994 uvedli stalni nadzor območja z urnikom obiska. Ob vhodih so postavili informacijski tabli o spomeniku. Delavci podjetja Givo so leta 1995 prepleskali arkade, odstranili grafite, obnovili polomljene spomenike, jih kemično očistili in peskali. Varnostniki so noč in dan varovali območje. Varovanje Navja so leta 1997 ukinili.
Dnevnik je 3. 6. 1999 poročal, da so restavratorji obnovili spomenike Matije Čopa, Valentina Vodnika, Jožefa Ressla in Frančiška Ksaverija Karuna, duhovnika trnovske župnije.
2001 je mestni svetnik dr. Janez Vrbošek dal pobudo, da bi uredili spominski park in postavili spomenik vsem umrlim za Slovenijo oziroma spomenik neodvisni Sloveniji. To bi napravili tako, da bi razširili zahodni vhod v Navje in ga povezali z Akademskim kolegijem. V povezovalnem delu bi stal spomenik. Predlagal je tudi, da bi spremenili status Navja iz lokalnega v spomenik nacionalnega pomena. Preimenovali bi ga v Gaj zaslužnih Navje.
