Henrik Nissen var sønn av Hartvig Nissen. Han var elev ved arkitekt Wilhelm von Hannos tegneskole i Kristiania i årene 1867–69 og samtidig ved Den kongelige tegneskole. 1869-70 var han elev ved Berliner Bauakademie, men ble avbrutt av den fransk-tyske krig i årene 1870-71. I denne perioden var Nissen igjen elev hos von Hanno, og samtidig hospiterte han i bygningsfag og kjemi ved Den militære høyskole i Kristiania. Ved avslutningen av den fransk-tyske krig returnerte Nissen til Berlin, der han igjen var elev ved Bauakademie frem til 1874. Han gikk også en tid i murerlære.
Henrik Nissen ble ansatt hos arkitektene Paul Due & Bernhard Steckmest i Kristiania i 1874, der han medvirket i utformingen av Steen & Strøms forretningsgård som brant ned i 1929. Nissen etablerte egen praksis i Kristiania i 1875 og samarbeidet samtidig (1878–85) med arkitekt Holm Munthe. Dette kompaniskapet resulterte blant annet i Christiania bad (1881–83, revet 1931), Otto Andersens skole (Uranienborgveien 7, 1884, nedbrent 1909) og Kristiania handelsgymnasium (Munchs gate 4, 1883-85).
