Han var sønn av sogneprest Lauritz Christian Holsøe (1789-1862) og Vilhelmine Euphrosyne Margrethe, født Feddersen (1797-1871).
Holsøe arbeidet først som murer og ble murersvenn i 1846. Han tegnet privat hos G.F. Hetsch og gikk deretter på Kunstakademiet i København i årene 1842-49 og 1851-52 (avbrutt av hans deltakelse i første slesvigske krig 1849-50). Han vant den lille sølvmedalje i 1847 og avsluttede i 1853 studiene på Kunstakademiet med den store sølvmedalje. Han arbeidet deretter sammen med Bernhard Seidelin, blant annet med Helsingør rådhus (1853-55). Han konkurrerte for å få gullmedalje, men ute å lykkes. Hans møte med Johan Daniel Herholdt og Herholdts inspirasjon fra italiensk renessanse satte også varige spor Holsøes arkitektur. I 1848 og 1853 deltok han i Charlottenborg Forårsudstilling, og i 1859 foretok han en studiereise til utlandet.
Han drev egen arkitektvirksomhet fra 1855, og 1860-61 sto han for han Marienlyst Badehotel, 1875-76Ugerløse kirke og i årenes løp en rekke villaer og private hus i og ved ulike danske byer, samt posthusene i Årup, Odense, Fåborg, Assens, Thisted, Skælskør og Helsingør.
Hans hovedvirksomhet var som jernbanearkitekt. I årene fra 1861 til 1892 var han ansatt ved Indenrigsministeriets kontroll med statsbanene og sto for oppføringen av alle stasjonsbygningene på de jysk-fynske baneanlegg (bortsett fra strekningen Aarhus-Randers og en rekke jernbanegårder tegnet av Thomas Arboe) og senere portalene ved Masnedsundbroen, samt de nye stasjonsbygningene i Lyngby og Helsingør (begge sammen med Heinrich Wenck) samt bygningene på strekningerne Slagelse-Næstved og Dalmose-Skælskør. Ved de fleste av disse bygningene tok Holsøe utgangspunkt i med Herholdts københavnske banegård (Københavns andre banegård 1863-64) og anvendte murstein som hovedmateriale.
Holsøe giftet seg 15. mai 1862 på Frederiksberg med Emilie Charlotte Klentz (født 3. august 1833 i København, død 1. november 1905 i Lyngby), datter av bakermester Gotfred Christian Vilhelm Klentz og Ane Cathrine Drastrup.
Stasjonene på Slagelse-Næstved banen og Skælskørbanen (1891-92, sammen med Heinrich Wenck): Dalmose stasjon, Sandved stasjon, Skælskør stasjon med posthus m.fl.
Vanntårnet ved Skørping stasjon (1898, oppført etter Holsøes tegning, fredet)
Tilskrivninger
En rekke mindre stasjonsbygninger på statsbanestrekninger, bl.a. Skanderborg-Silkeborg.