Čitalnica je sprva gostovala v novomeških gostilnah, ki pa za njeno kulturno in tudi politično delovanje niso mogle nuditi ugodne pogoje. Zaradi potrebe po lastnih prostorih je med čitalničarji vzniknila ideja o gradnji lastnega Narodnega doma.
Za ta namen je Čitalnica konec leta 1872 kupila gradbeno parcelo in že junija leta 1873 so položili temeljni kamen. Vendar pa se je gradnja zaradi pomanjkanja finančnih sredstev zavlekla kar za nekaj let. Dokončno je bil Narodni dom končan in izročen svojemu namenu šele leta 1885 in takrat se je Narodna čitalnica končno preselila v lastne prostore.
Narodni dom v Novem mestu je bil kot prvi te vrste na Slovenskem zgrajen zaradi potrebe novomeške čitalnice po lastnih prostorih. Temeljni kamen je bil položen junija 1873 in že naslednje leto je bila stavba pod streho. Uporabi predano pa je bilo zgolj pritličje. Gradnja se je le počasi nadaljevala, dokler niso leta 1884 v ta namen ustanovili delniško družbo Prvi Narodni dom, ki je za zbiranje sredstev izdala delnice. Že naslednje leto se je gradnja Narodnega doma uspešno zaključila. Edina ohranjena risba načrta vhodnega pročelja Narodnega doma je delo zagrebškega stavbenika Alfreda Kappnerja. Napis nad vhodnimi vrati se je ob prenosu lastništva na sokolsko društvo po letu 1925 spremenil v Sokolski dom.
