Henryk Mittelstaedt urodził się 19 maja 1936 roku w majątku ziemskim Czerwonka koło Sochaczewa (Polska). Jego ojciec Kazimierz, z wykształcenia inżynier rolnik, był administratorem majątku, który należał do państwa Grzybowskich. W 1939 roku, jeszcze przed wybuchem wojny – a już po tym jak ojciec, jako porucznik rezerwy kawalerii, został zmobilizowany – przenieśli się do Karskich, majątku rodzinnego matki na Podlasiu. Matka – Teresa Mittelstaedt (z domu Głogowska) zajmowała się dziećmi. Henryk Mittelstaedt ma starszą siostrę Danutę.
Ojciec Henryka Mittelstaedta został wzięty do niewoli przez żołnierzy Armii Czerwonej i internowany na Litwie, następnie osadzony w obozie w Starobielsku. W 1942 roku opuścił ZSRR wraz z armią generała Władysława Andersa, z którą przebył kampanię na Środkowym i Bliskim Wschodzie i we Włoszech jako dowódca (w randze rotmistrza) Kompanii Transportowej w II Dywizji Pancernej. Brał udział w walkach pod Ankoną i Monte Cassino.
Po wybuchu wojny Henryk Mittelstaedt z matką, siostrą, babcią oraz wujem mieszkał w Karskich. Tam podczas okupacji rozpoczął naukę w szkole powszechnej. Jego matka zaangażowana była w działalność Armii Krajowej. W majątku aresztowany został wuj, który zginął następnie w obozie koncentracyjnym Ravensbrück. Po wprowadzeniu reformy rolnej w 1944 roku majątek został rozparcelowany, a rodzina zmuszona do wyjazdu. Trafili do pobliskiej wsi Wyrozęby, gdzie znaleźli kwaterunek w domu chłopskiej rodziny. Tam matka zajmowała się wyrobem cukierków. Po krótkim czasie pobytu na miejscu, ze względu na powtarzające się oskarżenia kierowane wobec matki o zły wpływ na miejscową ludność, rodzina ponownie musiała wyjechać, tym razem przeniosła się do Siedlec. Na miejscu matka zajmowała się produkcją butów. Po około półtora miesiąca wyjechali do Warszawy (oprócz babci, która wyjechała do rodziny we Wrocławiu), gdzie zamieszkali u dalekich krewnych (w domu przy ulicy Czerwonego Krzyża na Powiślu). Matka pracowała jako kierowniczka kuchni w firmie „Mostostal” przy odbudowie mostu Poniatowskiego.
Po pewnym czasie matka Henryka Mittelstaedt zdecydowała się na ucieczkę z Polski, by połączyć się z mężem, z którym nawiązała kontakt i który pozostał na Zachodzie. Pierwsza próba ucieczki skończyła się niepowodzeniem. W celu realizacji drugiej próby kupiła fałszywe dokumenty wyjazdowe wypisane na obywateli Francji. W 1946 roku wraz z dziećmi dołączyła do grupy repatriantów francuskich; opuścili Warszawę, by przez czeską Pragę, a następnie Norymbergę dotrzeć ostatecznie do Włoch. W kwietniu 1946 roku nastąpiło spotkanie z mężem, który w tym czasie służył we Włoszech jako dowódca Kompanii Transportowej w II Dywizji Pancernej. Rodzina przez krótki okres mieszkała na południu Włoch w Bari. Henryk Mittelstaedt rozpoczął naukę w polskiej szkole z internatem w miasteczku Barletta (do czerwca 1946). Ponieważ dywizja ojca została przeniesiona na północ, w okolice Maceraty, na okres letni przeniosła się tam również jego żona z dziećmi.
Jesienią 1946 roku dywizja została ponownie przeniesiona, tym razem do Wielkiej Brytanii. Tu Henryk Mittelstaedt przez półtora roku uczęszczał do miejscowej szkoły. W 1947 roku nastąpiła demobilizacja Polskich Sił Zbrojnych na Zachodzie. Po dwóch latach pobytu w Anglii rodzice podjęli decyzję o wyjeździe do Argentyny. W kwietniu 1948 roku rodzina dotarła drogą morską do Buenos Aires, gdzie przez trzy tygodnie mieszkali w Hotelu Imigracyjnym na Retiro, następnie w wynajętym domu. Ojciec początkowo pracował fizycznie w warsztacie mechanicznym, następnie warsztacie samochodowym, w końcu znalazł zatrudnienie w administracji.
Już w Argentynie Henryk Mittelstaedt ukończył naukę w szkole powszechnej, następnie skończył sześcioletni kurs Średniej Szkoły Przemysłowej. Po jej ukończeniu rozpoczął studia na Wydziale Inżynierii Elektrycznej Uniwersytetu Państwowego w Buenos Aires. Podczas studiów podjął pracę w firmie „Elektrodinie” (dawny Siemens). W młodych latach należał do polskiego harcerstwa w Argentynie, był także członkiem polskiego chóru im. Fryderyka Chopina, członkiem założycielem i kilkakrotnym prezesem Polskiego Stowarzyszenia Absolwentów Wyższych Uczelni. Bierze czynny udział w działaniu Biblioteki im. Ignacego Domeyki. Za swą działalność społeczną, Henryk Mittelstaedt otrzymał od Rządu Rzeczypospolitej Polskiej Krzyż Zasługi oraz Kawalerski Order Odrodzenia Polski (Polonia Restituta). W 1976 roku ożenił się z Jolantą Demczuk. Mają dwie córki: Marię oraz Irenę. Mieszkają w Acassuso koło Buenos Aires.
