Že leta 1890 so začeli graditi odsek državne ceste, danes Ljubljanska cesta, mimo mestnega pokopališča in jo vsekali v južno pobočje Marofa nad reko Krko proti vasi Bršljin. Cesta je nadomestila strmo deželno cesto proti Ljubljani, danes Kettejev drevored. Izognila se je precejšnjemu vzponu čez marofski hrib, ki je tedaj od prevoznikov zahteval drago in zamudno menjavo vprežnih živali. Med gradnjo ceste, ki so jo poimenovali Kolodvorska, so naleteli na halštatski, tri latenske in večje število rimskih grobov. S tem odkritjem se je pričela bogata zgodovina arheoloških raziskovanj v Novem mestu.
Novomeščani so si želeli imeti kolodvor čim bliže svojih domov, a ker Novo mesto objema reka Krka in nad njim bdi hrib Marof, prostora zanj ni bilo veliko. Občinski mestni svet si je dolgo prizadeval, da bi bila železniška postaja v obsegu mesta, ali vsaj v mestnem pomirju katastrske občine. Za glavniške delnice družbe Dolenjskih železnic si je pri Ljubljanski mestni hranilnici izposodil 14 000 goldinarjev ter nakup pogojeval z želeno umestitvijo kolodvora.
Na ljubljanskem magistratu je 28. aprila leta 1891 potekalo posvetovanje o nadrobnem načrtu lokacij železniških postaj dolenjske proge. Seje se je udeležilo več zastopnikov iz različnih občin. Novomeški župan Albin Poznik in njegov svetovalec sta na sestanku predstavila znane zahteve o umestitvi postaje, ki so jih prisotni vzeli na znanje. Domov sta se vrnila brez dokončne odločitve, a naposled njuni zahtevi ni bilo ugodeno.
Naposled so nestrpni Novomeščani z zadovoljstvom le lahko prebrali:
Dolgo smo čakali, dolgo upali in se bali – slednjič se nam vendar le izpolni želja. Da res, tako so nas storile prejšnje neizpolnjene obljube maloverne, da prav do zadnjega časa nismo verovali v dolenjsko železnico; priprosti ljudje še celo potlej niso hoteli verjeti, da prižvižga hlapon tudi do Novega Mesta, ko se je jela proga proti Kočevju vže graditi. – A sedaj je istina tukaj. Nekaj dni se vže vozi k nam orodje gospoda povzetnika Ceconia, Gajška in drugih, ki so z mnogimi inženirji dospeli v naše mesto.
Gradnja dolenjske proge je zahtevala precejšnjo delovno silo. Zaradi njenega pomanjkanja so zaposliti tudi prisilne delavce in zapornike. Železnico so pomagali graditi tudi številni tuji delavci, ki so zlasti zaradi slabega plačila, ki naj ne bi zadostovalo niti za preživetje, povzročali izgrede. Mestni stražniki so tako občinsko vodstvo prosili za dodatno oborožitev: »… da potrebujemo za čas gradnje dolenjske železnice, kot na straži od mesta proti kolodvoru zvečer v noči še posebno, orožje revolverje ali puške, ker za brambo pri napadu so naše sablje preslabe …«
