Budynek dworca kolejowego w Kamiennej Nowej powstał w latach 1897--1899 wraz z budową linii kolejowej Grodno--Augustów--Suwałki--Olita--Orany, której otwarcie nastąpiło 13 maja 1899 r. Decyzja o budowie tej trasy zapadła w czerwcu 1895 r. Linia ta była zbudowana przez Rosjan jako militarna kolej okrężna. Odłączała się ona od Magistrali Petersburskiej na stacji Łosośna, zmieniając kierunek na północny zachód.
Kolejnymi stacjami były Bielany, położone w pobliżu Nowego Dworu, następną zaś Harasimowicze (później nazwa Różanystok), zlokalizowane w pobliżu Lipska i Dą-browy Białostockiej. Stacja kolejowa w Kamiennej Nowej była ostatnią stacją tej linii w granicach guberni grodzieńskiej, bowiem rzeka Biebrza oddzielała gubernię gro-dzieńską od suwalskiej. Znaczne odsunięcie stacji tej linii od większych ośrodków miej-skich sprawiło, że magistrala miała niewielkie znaczenie gospodarcze zarówno przed I wojną światową, jak i w okresie międzywojennym. Odcinek kolei Grodno--Suwałki został po II wojnie światowej przecięty granicą państwową. Linia została zamknięta i rozebrana na odcinku Grodno--Kamienna Nowa, a Suwałki i Augustów aż do 1964
r\. nie miały bezpośredniego połączenia kolejowego z Białymstokiem. Dopiero w latach 1960--1963 zaczęto budować połączenie kolejowe z Kamiennej Nowej do Sokółki. No-wego znaczenia stacja kolejowa Kamienna Nowa nabrała w 1964 r., kiedy ukończono magistralę kolejową biegnącą z Sokółki poprzez Różanystok i Dąbrowę Białostocką do Augustowa i Suwałk.
Dworzec kolejowy został wybudowany w końcu XIX w. na dawnych gruntach wsi Kamienna i nosił nazwę Stacja Kamienna. Jest to budynek murowany z żół-tej cegły, na fundamencie z ciosów kamiennych, wzniesiony na rzucie prostokąta, z ryzalitem środkowym w elewacji frontowej od zachodu i dwoma pseudoryzalitami oraz centralnie usytuowaną przybudówką w elewacji od strony torów. Budynek jest
Budynek dworca w Kamiennej Nowej
jednokondygnacyjny, nakryty czterospadowym dachem. Jego elewacje rozczłonkowa-ne są pilastrami z wycinanymi ozdobnie płycinami na trzonach i dekorowane bogatym detalem z żółtej cegły. Składają się nań: plastycznie rozbudowane szczyty w ryzalitach, dekoracyjne zwieńczenia pilastrów, fryz z ceglanych kolumienek obiegający budynek, kostkowe gzymsy kordonowe oraz oprawa otworów okiennych i drzwiowych. Dwo-rzec reprezentuje budownictwo ceglane charakterystyczne dla obiektów koszarowych i kolejowych z przełomu XIX i XX w.