Einar Tufte-Johnsen var en av de unge førkrigsoffiserene i det nye flyvåpenet som gjennom fem års krigsinnsats la grunnlaget for den storstilte utbyggingen av et norsk luftforsvar innen militæralliansen NATO under den kalde krigen. Som høyeste offiser i Bodø hadde han våren 1960 direkte befatning med den såkalte U-2-affæren, da et amerikansk spionfly ble skutt ned over Sovjetunionen på vei til Bodø. Senere i 1960- og 1970-årene tjenestegjorde han innen Luftforsvaret og NATO både i Norge og i utlandet.
Tufte-Johnsen tok examen artium 1935 og ble året etter utdannet som vernepliktig flyger ved Hærens flyskole på Kjeller ved Lillestrøm. Han valgte en militær karriere, og etter Krigsskolen 1938 ble han ansatt som løytnant i hæren. Vinteren 1939–40 var han lærer ved flyskolen, og etter det tyske overfallet deltok han i evakueringen av skolens fly og mannskaper via Østerdalen til Sverige, hvor han ble internert. Mai 1940 ledet han en gruppe fra flyvåpenet som reiste via Finland og Kirkenes til Bardufoss for å delta på Narvik-fronten. Her ble han beordret som ny sjef for Hålogaland flyavdelings speideving frem til felttoget ble avsluttet i juni.
Tufte-Johnsen var en av 22 frivillige fra Hærens flyvåpen som fulgte regjeringen Nygaardsvold og kong Haakon i eksil med krysseren HMS Devonshire fra Tromsø. Tufte-Johnsen ble en av organisatorene av det nye luftforsvaret i eksil, først ved treningsleiren Little Norway i Toronto, Canada, og siden i Flyvåpnenes felleskommando i London. Han ble kaptein 1941 og major 1944. Etter krigen var han først assisterende luftattaché i London en tid og arbeidet 1946–49 ved Luftforsvarets overkommando, hvor han ble oberstløytnant 1947. Han var sjef for Gardermoen flystasjon 1949–51.
Høsten 1950 ledet Tufte-Johnsen 336 Skvadron til den første norske deltakelse i en luftmilitær øvelse i Storbritannia etter krigen. Under trening to dager før avreise kolliderte hans Vampire-fly i luften med en annen Vampire jetjager. Han unnslapp med livet i behold, mens den andre flygeren omkom.
Tufte-Johnsen var sjef for operasjonsstaben i Luftforsvarets overkommando 1951–56, i en tid da Luftforsvaret ble dramatisk omformet gjennom amerikansk våpenhjelp og Norges NATO-medlemskap. I disse årene ble Luftforsvarets flystyrke tredoblet, og en rekke nye flystasjoner ble bygd. Tufte-Johnsen ble oberst 1951 og generalmajor 1953.
1956 ble han sjef for Luftkommando Nord-Norge i Bodø, som gradvis ble tyngdepunktet i det norske luftforsvaret. Her ble han høsten 1958 vert for to–tre U-2 etterretningsfly fra amerikanske CIA, som i største hemmelighet spionerte på sovjetisk atomvåpentesting på Novaja Semlja. Da et U-2-fly ble skutt ned over Sverdlovsk på vei til Bodø 1. mai 1960 og skapte internasjonal krise, viste det seg at Tufte-Johnsen i denne saken hadde mottatt ordre direkte fra Etterretningsstaben, mens sjefen for Luftforsvaret var holdt utenfor.
Tufte-Johnsen hadde 1959 tatt Forsvarets Høyskole, og 1962 ble han luftkommandør ved NATOs Nordkommando på Kolsås. Han ble generalløytnant 1963 og var til 1966 også nestkommanderende på Kolsås, før han ble sjef for NATO Defence College i Paris. Da president de Gaulle 1967 trakk Frankrike ut av NATOs militære samarbeid, ledet Tufte-Johnsen flyttingen av skolen til Roma.
Han kom tilbake til Norge 1968 som sjef for Luftkommando Sør-Norge og ble også formann for flyplasskomiteen for Oslo-området, som utredet en rekke alternativer til den da jetflystøybelastede Fornebu. Til tross for Tufte-Johnsens engasjement og arbeidskapasitet viste det seg at tiden ikke var moden for politiske beslutninger om ny hovedflyplass.
Da forsvarets kommandostruktur ble reorganisert 1971, ble Tufte-Johnsen den første øverstkommanderende i Sør-Norge som både hadde regional norsk og NATO-kommando i fredstid. Han avsluttet sin militære karriere med tre år som sjef for den norske militærmisjonen og forsvarsattaché i Washington, D.C. til han ble pensjonist 1980. Han ble utnevnt til kommandør av St. Olavs Orden 1972, var innehaver av Deltagermedaljen med rosett og hadde en rekke utenlandske ordener og dekorasjoner.