Johan Fritzner fæddist á bænum Myren á Askey við Björgvin. Foreldrar: Werner Andreas Fritzner (1777–1863) tollvörður og kona hans Cecilie Cathrine Christie (1784–1827).
Hann gekk í skóla í Björgvin, þar sem faðir hans fékk stöðu sem yfirtollvörður. Hann hóf nám í Háskólanum í Kristjaníu, 16 ára gamall, og nam þar guðfræði, þó að áhugamál hans allt frá æskuárum væru á sviði málfræði og sögu. Á háskólaárunum beindist áhugi hans að norrænum málum og sögu Noregs, einkum menningarsögu. Fór hann þá þegar að skrifa upp og safna efni til síðari nota. Á vorin og haustin fór hann fótgangandi milli Kristjaníu og Björgvinjar, og notaði þá tækifærið til að safna slíku efni: Hann lýsti þjóðháttum, skráði þjóðsögur og ævintýri, og lýsti sérkennum alþýðumálsins á hverjum stað. Hann komst snemma á þá skoðun að norsku mállýskurnar væru eðlileg þróun frá fornmálinu, sem hann hafði kynnst í hinum fornu norsk-íslensku bókmenntum.
Fritzner tók embættispróf í guðfræði 1832, og var síðan tvö og hálft ár í Kristjaníu til þess að geta sinnt áhugamálum sínum. En hann fékk enga stöðu þar og þáði því kennarastarf við Dómkirkjuskólann í Björgvin, 1835. Í frístundum sínum sökkti hann sér niður í athuganir á hinu forna tungumáli Norðmanna. Hann safnaði einnig gömlum skinnbréfum, sem þá voru enn til á stöku stað.
Eftir þrjú ár í Björgvin varð Fritzner sóknarprestur í Vadsø í Finnmörku. Aðalástæðan var sú að hann vildi kynna sér þar samísku og finnsku meðal innfæddra. Rasmus Kristján Rask hafði haldið því fram, að málfarsleg áhrif í Noregi væru fyrst og fremst frá samísku yfir í norsku, en Fritzner var kominn á þá skoðun að því væri öfugt farið. Vorið 1839 tók Fritzner við prestakallinu og sinnti hinu nýja starfi sínu strax af miklum áhuga. Þegar hann hafði náð tökum á tungumálinu fór hann að predika yfir Sömum og Kvenum á samísku og finnsku. Fyrsta ritsmíð sem Fritzner lét prenta (1845) var einmitt um samísku; gagnrýni á rit eftir Nils Vibe Stockfleth: Grammatikk i det lappiske Sprog. Fritzner varð prófastur í Austur-Finnmörku 1841.
Árið 1845 varð Fritzner sóknarprestur í Lier í Buskerud héraði, skammt frá Kristjaníu (Osló), og 1848 í Vanse í Vestur-Agðafylki, sem er nokkru fjær. Hann fór til Kristjaníu eins oft og hann gat, til þess að halda tengslum við vísindamenn þar og kynnast nýjum. Þetta varð til þess að margir háskólamenn fengu vitneskju um hvað þessi lærði prestur var að fást við. Þeir hvöttu Fritzner til að fullvinna orðasöfn sín, með það að markmiði að gefa út orðabók. Árið 1860 hóf hann að búa orðabókina undir prentun og kom fyrsta heftið út í Kristjaníu haustið 1862. Um sama leyti flutti hann sig um set og varð sóknarprestur í Tjølling á Vestfold, sem var mun nær Kristjaníu. Fyrstu útgáfu orðabókarinnar var lokið 1867: Ordbog over det gamle norske Sprog (eitt bindi). Hún var þá besta hjálpartækið fyrir þá sem vildu rannsaka mál hinna fornu norsk-íslensku bókmennta, einkum í lausu máli.
Fritzner var ljóst að orðabókin var frumsmíð og að auka þyrfti við hana og gefa hana út aftur. Hann sagði því af sér prestsembætti 1877, 65 ára gamall, til þess að geta helgað sig tveimur stórvirkjum, þ.e.a.s. nýrri útgáfu af orðabókinni, og útgáfu á hinu umfangsmikla safni sínu af þjóðfræðilegu og menningarsögulegu efni. Sama ár veitti ríkisstjórnin honum 3.600 króna eftirlaun. Árið 1878 fluttist hann til Kristjaníu og hófst strax handa við verkið. Að jafnaði vann hann óslitið frá því klukkan 5–6 að morgni til 3–4 síðdegis, snæddi þá í faðmi fjölskyldunnar, og hélt svo yfirleitt áfram fram á kvöld. Fyrsta hefti orðabókarinnar kom út 1883, og næstu hefti komu með stuttu millibili. Verkið óx mjög í höndum hans, því að hann leitaðist við að taka allt það með sem honum virtist geta komið að gagni. Fyrsta bindi var lokið 1885, og öðru bindi 1891, þegar Fritzner var kominn á 80. aldursár. Hann hélt þó áfram verki sínu til 1893, þegar byrjað var að prenta 24. hefti orðabókarinnar. Þá fann hann að minnið var farið að gefa sig og að hann yrði að gefa verkið frá sér. Bað hann prófessor Sophus Bugge og tvo aðra vini sína að útvega hæfan mann til að halda verkinu áfram. Tók Carl Richard Unger þá að sér að búa til prentunar það sem eftir var af orðabókinni, og var henni lokið 1896.
Johan Fritzner dó 10. desember 1893, nær 82 ára gamall, eftir stutta sjúkdómslegu.
Hann giftist 1839, Anne Christine Qvale (8. apríl 1816 – 17. desember 1896); foreldrar hennar voru Andreas Qvale (1779–1820) sóknarprestur og Friderike Christianne Dithlevine Heltzen (1777–1820).
Nánar um Orðabók Fritzners
Árið 1972 kom út viðaukabindi við orðabókina (4. bindi), eftir Finn Hødnebø, með leiðréttingum og viðaukum.
Orðabók Fritzners hefur allt til þessa dags verið mikilvægasta hjálpartækið við rannsóknir á lausamáli hinna fornu norsk-íslensku bókmennta. Útskýringar Fritzners eru nákvæmar og studdar ítarlegum tilvitnunum í umrædd rit. Í sumum tilfellum varpa skýringarnar ljósi á menningarsöguna, eins og tíðkast í alfræðiorðabókum.
