Born in Copenhagen, he first trained as a stone mason before studying at the Royal Danish Academy of Fine Arts where he was awarded the grand silver medal in 1856. From 1851 to 1856, he worked as a draftsman for Michael Gottlieb Bindesbøll who he always considered to have been his main instructor.
From 1857 to 1862, he worked as an architectural designer for Ferdinand Meldahl who also influenced his style. He also worked for Johan Daniel Herholdt during the construction of Selchausdal Manor (1857) in Kalundborg, thus receiving insights for the most prominent architects of the day.
Klein was particularly fond of the Rosenborg style based on the Dutch Renaissance trends under Christian IV, crediting Bindesbøll for its prominent place in Danish architecture. From 1866 to 1872, he undertook substantial extensions to Bindesbøll's Lægeforeningens boliger social housing development in Copenhagen's Østerbro. His masterpieces include the Industriforeningen Building on Vesterbro (1872, now demolished) in the Italian Renaissance style, the Kunstindustri Museum in the Rosenborg style on Rådhuspladsen (1893), and the main building at the Ny Carlsberg Brewhouse (1901), also in the Italian Renaissance style.