Mittelholzer ble født 2. april 1894 i St. Gallen. Han fikk sitt flysertifikat i 1917, og i 1918 fullførte han sin utdannelse som militærflyver.
Den 5. november 1919 var han med å grunnlegge et flyfoto- og passasjerselskap, Comte, Mittelholzer og Co. I 1920 slo dette firmaet seg sammen med det økonomisk sterkere Ad Astra Aero. Mittelholzer var direktør og sjefspilot for Ad Astra Aero som senere ble Swissair.
Han gjennomførte den første flyvningen fra nord til sør over Afrika. Det tok ham 77 dager. Mittelholzer begynte i Zürich 7. desember 1926 og fløy via Alexandria og landet i Cape Town 21. februar 1927. Tidligere hadde han vært den første til å foreta en rekognosering av Spitsbergen i et Junkersmonoplan, i 1923.[6] Den 15. desember 1929 ble han den første til å fly over Mt. Kilimanjaro, og han planla å fly over Mount Everest i 1930.[7][8] I 1931 ble Mittelholzer utnevnt til teknisk direktør for det nye flyselskapet, Swissair, dannet av fusjon mellom av Ad Astra Aero og Balair.[9] Hele sitt liv har han utgitt mange bøker om flyfotografering.
Han døde i 1937 under en klatreulykke på en ekspedisjon i Hochschwabfjellene i Steiermark i Østerrike.[10]
Blant andre Swissair-pionerer ble han minnet i et sveitsisk frimerke i januar 1977.
Im Flugzeug dem Nordpol entgegen: Junkers ' sche Hilfsexpedition für Amundsen nach Svalbard, 1923 (med Kurt Wegeners, Adolf Miethe, Hans Boykow). Orell Füssli, 1924.
Die Schweiz aus der Vogelschau: 274 Abbildungen aus der Sammlung von Walter Mittelholzer (med Otto Flückiger. Eugen Rentsch, 1926.
Persienflug (med Otto Flückiger). Orell Füssli, 1926.
Kilimandjaro Flug. Orell Füssli, 1930.
Alpenflug (med F. Hass, Hans Kempf, Willi Fritz Burger). Orell Füssli, 1930.
Mittelmeerflug, mit 120 Fliegeraufnahmen og en Einleitung (med Gustav Ehrhardt). Rascher & cie, 1930.
Tschadseeflug: Mit dem drei-motorigen Fokker der Swissair durch die Sahara zum Tschadsee (med Auguste Piccard). Schweizer aero-revy, 1932.
Abessinienflug: Mit dem dreimotorigen Fokker an den Hof des Negus Negesti. Schweizer aero-revy, 1934.
Fliegerabenteuer (med Willi Rickmer Rickmers, Werner von Langsdorff). Brockhaus, 1938.
^«Flight Over Mount Everest Is Planned by Swiss Flier». New York Times. 7. august 1930.
^«Swiss Finds Backers for Everest Flight; Mittelholzer Says His Attempt Awaits Building of Motors Efficient at 15,000 Feet». New York Times. 16. august 1930.