Johan Fritzner var i sin ungdom prest i Finnmark, der han også studerte samenes språk og kultur. Senere kombinerte han prestegjerningen i Sør-Norge med studiet av norrønt språk. Hans hovedverk er Ordbog over det gamle norske Sprog, den største ordbok som er laget over det norrøne ordforrådet.
Fritzner tilbrakte sine første barneår på tollstedet Bukken ytterst på Bergenshalvøya, men da han var 9 år gammel, ble faren utnevnt til overtollbetjent i Bergen og familien flyttet dit. Moren tilhørte den gamle bergensslekten Christie og var kusine av stortingspresident W. F. K. Christie. Fritzner ble 1828 dimittert fra Bergens katedralskole til universitetet i Christiania, hvor han begynte å studere teologi. Etter cand.theol.-eksamen 1832 fortsatte han med studier i norrøn filologi og historie i et par år. Han fikk god attest for sine grundige kunnskaper av Rudolf Keyser, grunnleggeren av norrønstudiet ved universitetet. Etter tre år som lærer ved katedralskolen i Bergen ble han 1838 utnevnt til sogneprest i Vadsø og var dessuten prost i Øst-Finnmark fra 1841. Han var residerende kapellan i Lier 1845–48, sogneprest i Vanse og Farsund 1848–62 (og prost i Lister prosti fra 1861). Sin siste prestestilling hadde han som sogneprest i Tjølling fra 1862 til han tok avskjed med pensjon 1877.
Helt fra skoledagene hadde Fritzner vent seg til å skrive ned ting som interesserte ham, sagn og kulturhistoriske opplysninger om skikk og bruk, og ord og uttrykk i norrøne tekster. I studietiden gikk han til fots til Bergen og tilbake til Christiania i feriene og skrev ned ord og ordformer som han hørte av folk han traff. Ivar Aasen sier i sin arbeidsrapport for 1860 at han har fått nyttige opplysninger av Fritzner, som “har været en opmerksom Iagttager af det nulevende Sprogs Tilstand paa de Steder, hvor han har opholdt sig”.
Fritzner søkte stillingen i Vadsø bl.a. fordi han ville sette seg inn i finsk og samisk språk og studere samenes kultur. Resultatene av sine studier publiserte han bl.a. i de to artiklene Beskrivelse over de i Østfinmarken forekommende hedenske Begravelser (1846) og Lappernes Hedenskab og Trolddomskunst sammenholdt med andre Folks, især Nordmændenes, Tro og Overtro (1876), et pionerarbeid i sammenlignende religionsforskning.
Hans omfattende samlinger av språklig materiale ble grunnlag for Ordbog over det gamle norske Sprog, i ett bind, utgitt heftevis 1862–67. I løpet av de første 60 år av 1800-tallet ble store deler av den islandske og norske prosalitteratur fra middelalderen utgitt, og det var fra disse utgavene Fritzner hadde hentet sitt materiale. Skaldespråket er ikke tatt med, fordi det allerede var behandlet i Sveinbjörn Egilssons Lexicon poëticum (1854–60). Fritzners ordbok fikk mange lovord og ble snart utsolgt, og han ble oppfordret til å sørge for et nytt opplag. Men først da han tok avskjed og flyttet til hovedstaden 1878, kunne han gå i gang med en omarbeidet og sterkt utvidet utgave. Den ble utgitt i tre bind på til sammen ca. 2900 sider – mer enn tre ganger så stor som første utgave – fra 1883 til 1896, og den er fremdeles den mest fullstendige ordbok over norrønt prosaspråk.
Grundighet og nøyaktighet kjennetegner Fritzners ordbok. Særlig ved mindre vanlige ord viser han med mange sitater forskjellige betydninger og nyanser av ordene, og han peker på paralleller i andre gammelgermanske språk, gresk og latin, men særlig ved ord for konkreter har han mange henvisninger til tilsvarende ord fra norske målfører. Enkelte artikler kan være små kulturhistoriske avhandlinger, f.eks. hamarr, helvíti, lýsigull.
Da Fritzner døde 1893, hadde han lest korrektur på første tredel av tredje bind; bindet ble fullført av hans venn og medarbeider C. R. Unger og kom ut 1896.
Fritzner var valgt som suppleant til Stortinget fra Lister og Mandals amt 1862–63, men slapp å møte. Sammen med Sophus Bugge og Oluf Rygh var han medlem av den offentlige kommisjonen som ble oppnevnt 1878 for å revidere navnene i matrikkelen. Han var medlem av Videnskabs-Selskabet i Christiania (nå Det Norske Videnskaps-Akademi) fra 1864 og av Det Kongelige Danske Videnskabernes Selskab fra 1888. Han ble utnevnt til ridder av St. Olavs Orden 1879 og æresdoktor ved Københavns universitet samme år.