His most notable works include Helsingør station and Nyboder Girls' School.
Seidelin was born at Sankt Hans Hospital in Roskilde, the son of medical doctor at Sankt Hans Hospital Johannes Henrik Seidelin and Johanne Marie Petersen.
He apprenticed as a mason before enrolling at the Royal Danish Academy of Fine Arts in 1840.
He initially studied under G. F. Hetsch and later under Michael Gottlieb Bindesbøll who was working on Thorvaldsens Museum.
He also designed a number of large villas for the upper middle class in the new districts that emerged outside Copenhagen's decommissioned fortification ring.