Před zřízením nemocnice v Novém Městě byli nemocní nejčastěji převáženi do nemocnic v Poličce a Německém (dnešním Havlíčkově) Brodě, ale někteří i do Brna. Sanitní automobil byl v té době provozován místním hasičským sborem, který měl pro poskytování první pomoci sestaven a vyškolen tzv. samaritní oddíl, vybavený základními zdravotnickými pomůckami.

Na prosincovém zasedání obecního zastupitelstva v roce 1935 bylo sděleno, že vedení města podalo žádost k zemskému úřadu v záležitosti zřízení okresní nemocnice v Novém Městě na Moravě. Kladné vyjádření k této žádosti ze strany zemské rady bylo oznámeno na zasedání zastupitelstva v únoru 1936. Bylo sděleno, že po prozkoumání míst vhodných pro její stavbu bylo Nové Město radou vyhodnoceno jako nejpříhodnější. Podmínkou pro uskutečnění projektu bylo současně dokončení pokládky vodovodu v Novém Městě. Zastupitelstvo se jednohlasně shodlo, že společně budou všichni usilovat o realizaci stavby nemocnice, od jejíhož uskutečnění si mimo jiné slibovali i hospodářské povznesení města.

Problém však, stejně jako u většiny významných komunálních projektů, představovaly finance. Okresní úřad sice se stavbou nemocnice v Novém Městě plně souhlasil, ale sám na její zřízení nebyl schopen poskytnout dostatečný kapitál. Úřad proto rozhodl, že pošle oběžník na všechny obce v okrese s prosbou, aby na stavbu libovolně přispěly. Po Novém Městě poté požadoval příspěvek ve výši 100 000 Kč. Nové Město pro tento účel využilo různých fondů, ve kterých mělo své finance uloženy. Tyto finanční rezervy byly současně podpořeny dobrovolnou sbírkou mezi obyvatelstvem. Na vybudování nemocnice byla také novoměstskému okresu povolena Zemským úřadem v Brně půjčka 2,5 milionu korun.

Je nutné zmínit, že nadšení ze stavby nemocnice v Novém Městě rozhodně nesdílela Bystřice nad Pernštejnem a Město Žďár, jelikož obě města taktéž o její zřízení usilovala a vedla za tímto účelem dlouhá jednání u příslušných úřadů a korporací. Jak již bylo zmíněno, stavba nemocnice pro dané město představovala významné zvýšení jeho důležitosti a prestiže jakožto zdravotního centra a znamenala také příslib hospodářských zisků do budoucna.

Definitivní rozhodnutí stavět nemocnici v Novém Městě na Moravě padlo 8. října 1936 a přípravné práce začaly již 14. října 1936. Stavba samotná byla zadána brněnské firmě stavitele Josefa Špačka za celkový obnos 2 319 043, 90 Kč.

Základní kámen ke stavbě nemocnice byl slavnostně položen 21. srpna 1938, a to za účinkování mužských pěveckých sborů místního hudebního spolku Smetana a bystřického Sokola. Předpokládalo se, že stavba bude dokončena během roku 1938, aby běžný provoz mohl začát hned od ledna 1940. Události, které přinesly roku 1938 a 1939, ale stavbu načas přerušily a k zahájení částečného provozu s příjmem pacientů nakonec došlo až 1. prosince 1940.

Jindřich Chatrný z Muzea města Brna komentoval architektův přínos následovně: „Bedřich Rozehnal je v Novém Městě na Moravě prezentován jako architekt, který změnil standard nemocničního prostředí. On vnesl do těchto staveb světlo, vzduch. Pacient se v takových prostorách cítil dobře. Byly to pavilony, které byly prosvětlené, měly promyšlenou koncepci provozu. Na svých projektech velmi často spolupracoval s týmem odborných lékařů.