Mittelholzer nació el 2 de abril de 1894 en San Galo, hijo de un panadero, y obtuvo su licencia de piloto privado en 1917. En 1918 completó su instrucción como piloto militar.

El 5 de noviembre de 1919 cofundó una empresa de aerofotografía y vuelos de pasajeros, Comte, Mittelholzer & Co. En 1920 esta empresa se fusionó con Ad Astra Aero, más fuerte financieramente. Mittelholzer fue director y piloto jefe de Ad Astra Aero, que más tarde se convertiría en Swissair.

Realizó el primer vuelo norte-sur a través de África. Tardó 77 días. Mittelholzer partió de Zúrich el 7 de diciembre de 1926, voló vía Alejandría y aterrizó en Ciudad del Cabo el 21 de febrero de 1927. Anteriormente, había sido el primero en realizar un reconocimiento aéreo serio de Spitsbergen, en un monoplano Junkers, en 1923.^[1]​ El 8 de enero de 1930 se convirtió en la primera persona en sobrevolar el Kilimanjaro; planeaba sobrevolar el monte Everest más adelante en 1930.^[2]​^[3]​ En 1931, Mittelholzer fue nombrado director técnico de la nueva compañía aérea llamada Swissair, formada a partir de la fusión de Ad Astra Aero y Balair.^[4]​ A lo largo de su vida publicó muchos libros de fotografías aéreas y comercializó sus expediciones a través de películas y de los medios de comunicación.^[5]​

Murió en 1937 en un accidente de alpinismo durante una expedición en el macizo de Hochschwab, en la cara suroeste de Stangenwand, en Estiria, Austria.^[6]​ Sus restos mortales fueron incinerados y enterrados en el panteón familiar del cementerio de Feldli, en San Galo.