John Brynildsen er mest kjent som leksikograf. Han utførte et pionerarbeid med sin innsamling av norske ord, og var den som først behandlet norsk riksmål som en egen språkform, uavhengig av dansk.
John Brynildsen tok klassisk examen artium 1870, examen philosophicum (med italiensk som tilleggsfag) 1871 og språklig-historisk embetseksamen 1875. Fra 1876 var han lærer i engelsk og fransk, fra 1896 også i tysk, ved Den Kongelige Norske Søkrigsskole i Karljohansvern (Horten), fra 1890 med tittel av dosent. Han virket her til sin avskjed 1922. Brynildsen var kjent som en fremragende lærer, som i alle år ikke forsømte en time. At kadettene i en del av skoleåret var ute på tokt, gav ham tid til egne studier, bl.a. med seks utenlandsopphold (London, Paris, Berlin). Han utgav også en rekke ord- og tekstsamlinger til skolebruk; hans første trykte arbeid var en Kortfattet Fransk Grammatik (1879).
1878 giftet John Brynildsen seg med sin kusine, forfatteren Benedicte Marsine Krag. Hennes far var fransklærer ved Krigsskolen, og moren hadde vært skuespillerinne ved de norske teatre i Bergen og Kristiania. De fikk fem barn.
I det offentlige liv deltok Brynildsen bl.a. som medlem av og formann i lignings- og overligningskommisjon og som formann i den lokale grunnlovsforening og i Horten og omegns riksmålsforening. Brynildsen var ivrig riksmålsmann og engasjerte seg særlig i motstanden mot rettskrivningsreformen av 1917. Han utgav 1918 brosjyren Vort Sprog og skrev tallrike avisinnlegg (i Gjengangeren, Dagbladet og Morgenbladet).
Sitt varigste ry vant Brynildsen seg som leksikograf, gjennom store ordbøker til og fra engelsk og tysk. Han var først medarbeider i to danske ordbøker, Dansk-Norsk-Engelsk Ordbog og Dansk-Norsk-Fransk Ordbog, og reviderte rektor J. Geelmuydens Engelsk-Norsk Ordbog. Hans første egne ordbok var Kortfattet Norsk-Engelsk Sø-ordbog.
1889–92 utkom Norsk-Engelsk Ordbog. Det var den første norske ordbok som behandlet ordforrådet i norsk riksmål som en egen språkform og ikke som et tillegg til dansk. Annenutgaven i 1917 var dermed den største riksmålsordbok før Norsk riksmålsordbok (NRO) utkom (1934–57), og NRO brukte den som en hovedkilde. En tredje utgave utkom 1927, etter Brynildsens død.
De viktigste av Brynildsens andre ordbøker var Tysk-norsk (dansk) ordbog, Engelsk-Dansk-Norsk Ordbog og Norsk-tysk ordbog. Den siste var basert på den norsk-engelske, med tillegg fra Brynildsens samlinger.
Brynildsens ordbøker var pionerarbeider der det norske materialet i stor utstrekning bygde på Brynildsens egne samlinger. Han samlet ord fra litteratur overalt hvor han til enhver tid befant seg, og søkte stadig opplysninger om ord og betydninger hos kolleger i inn- og utland og hos samtidens skjønnlitterære forfattere.
Brynildsens ordbøker er tett redigert, og for å sikre tilgjengeligheten gjennomførte han en mest mulig alfabetisk rekkefølge. Han la vekt på autentiske eksempler. I 1917-utgaven av Norsk-Engelsk Ordbog innførte han gjennomgangsfiguren «Mr. (eller Captain) Cold», som han lot gjennomgå varierte opplevelser knyttet til de norske oppslagsordene. Dette gjorde eksemplene til dels mer spesielle enn representative for norsk allmennspråk, som var den variant Brynildsen ønsket å prioritere, men de gjenspeiler en egenskap som Brynildsen la vekt på, at «denslags arbeider i første række forudsætter et godt humør».
Et problem for Brynildsen som leksikograf var at han på under 20 år måtte forholde seg til tre ulike rettskrivningsnormer. Det bidrog til hans konservative språkholdning. Han tok opp 1907-rettskrivningen og valgte blant valgfrie former «den, som syntes mig at stemme bedst med dannet, ukunstlet norsk talebruk» (fra forordet til Norsk-tysk ordbok, 1926), eller som var «mindst avstikkende» (forord til Norsk-Engelsk Ordbog, 1917). En ofte sitert setning fra 1917 er denne: «Overhodet kan det ikke ansees for nogen ulykke, om en far eller bedstefar fremdeles uten større anstøt kan læse, hvad hans søn eller sønnesøn har skrevet.» For ordenes uttale fulgte han 1910-utgaven av Ivar Alnæs' Norsk uttaleordbog, også etter at denne kom i revidert utgave 1926.
I løpet av 1920-årene gikk de fleste over til 1917-rettskrivningen (Aftenposten 1928, Morgenbladet fra 1931). Brynildsens konservative ortografi gjorde derfor at ordbøkene snart fikk en foreldet språkform som stod i motsetning til hans åpne holdning til å ta inn nye samtidsord. Senere leksikografer har utnyttet ordsamlingene og forklaringene i Brynildsens ordbøker.
1907 fikk Brynildsen den franske orden Officier de l'Instruction Publique, og ved Sjøkrigsskolens 100-årsjubileum 1917 ble han ridder av 1. klasse av St. Olavs Orden for «fortjenstfuld lærervirksomhet».