He was the son of Johan Henrik Nebelong and Anna Christine Schreyber.

[2] In 1819 he was admitted to the Royal Danish Academy of Fine Arts where he studied under German-born, Danish architect Gustav Friedrich Hetsch and won both the small and large gold medal, in 1833 and 1837 respectively.

Nebelong taught at the academy for several years before he went abroad on its travel scholarship from 1839 to 1842.

[1][3] After a few years as a teacher at the academy, he travelled to Paris, where he studied under Henri Labrouste, and then continued to Italy and Greece, before returning to Denmark in 1842.

Typically of the Historicist period, Nebelong worked in a number of different styles, including the late Neo-Classicism (Kolding Gymnasium, 1845–46), Gothic Revival (Slagelse Convent, 1857–59), and Romanesque Revival (Viborg Cathedral, 1863–76, completed by H.B.