Han var søn af sognepræst Lauritz Christian Holsøe (1789-1862) og Vilhelmine Euphrosyne Margrethe født Feddersen (1797-1871).
Holsøe startede som murer og arbejdede sig op. Han blev murersvend 1846; tegnede privat hos G.F. Hetsch og gik dernæst på Kunstakademiet i København 1842-49 og 1851-52 (afbrudt af hans deltagelse i Treårskrigen 1849-50). Han vandt den lille sølvmedalje i 1847 og afsluttede i 1853 sine studier på Kunstakademiet med den store sølvmedalje, hvorefter han arbejdede sammen med Bernhard Seidelin, for hvem han arbejdede som konduktør på Helsingør Rådhus (1853-55). Han konkurrerede forgæves efter guldmedalje. Hans møde med Johan Daniel Herholdt og dennes praktiseren af en arkitektur inspireret af italiensk renæssance satte sig sig varige spor i hans arbejder. 1848 og 1853 deltog han i Charlottenborg Forårsudstilling. I 1859 foretog han en rejse til udlandet.
Hans hovedvirksomhed var som jernbanearkitekt. Fra 1861 til 1892 var han ansat ved Indenrigsministeriets kontrol med statsbanerne og har opført alle stationsbygningerne på de jysk-fynske baneanlæg (undtagen strækningen Aarhus-Randers og undtaget en række banegårde tegnet af Thomas Arboe) og senere portalerne ved Masnedsundbroen, samt de nye stationsbygninger i Lyngby og Helsingør (begge sammen med Heinrich Wenck) samt bygningerne på strækningerne Slagelse-Næstved og Dalmose-Skælskør. Ved de fleste af disse bygninger har Holsøe, med Herholdts københavnske banegård (Københavns anden banegård 1863-64) som udgangspunkt, anvendt mursten som hovedmateriale.
Holsøe ægtede den 15. maj 1862 på Frederiksberg Emilie Charlotte Klentz (3. august 1833 i København - 1. november 1905 i Lyngby), datter af bagermester Gotfred Christian Vilhelm Klentz og Ane Cathrine Drastrup.
