Narodil se v Holicích v rodině lékaře Františka Holuba a jeho manželky Anny, rozené Ebertové. V roce 1857 se rodina přestěhovala do Pátku nad Ohří. V dětství četl africký cestopis Davida Livingstona, který jej podle jeho pozdějších slov silně ovlivnil. První ročník gymnázia studoval na německém reálném gymnáziu v Praze, další ročníky pak na německém gymnáziu v Žatci, kde maturoval v roce 1866. Chtěl studovat přírodní vědy a archeologii, ale na přání otce začal studovat na lékařské fakultě Karlo-Ferdinandově univerzitě, kde 24. února 1872 promoval a získal titul doktor medicíny.
Za podpory Vojtěcha Náprstka odjel 18. května 1872 na svou první cestu do jižní Afriky. Vyplul z anglického Southamptonu a po krátkém mezipřistání v Kapském Městě se vylodil 8. července v Port Elizabeth. Díky doporučení tamějšího rakouského konzula Adlera zde začal pracovat jako lékař v evropských rodinách. 26. srpna 1872 odešel vykonávat lékařskou praxi mezi městy Dutoitspan a Kimberley mezi hledači diamantů. V březnu 1873 se přidal ke konvoji místních lovců na dvouměsíční cestu – „vědecké safari“ na území bečuánského kmene, kde získal první zkušenosti s domorodci a výstrojí. Sestavil přírodovědnou sbírku, kterou ve dvaceti bednách odeslal Náprstkovi do Prahy.
3. listopadu 1873 vyrazil na druhou vědeckou výpravu se zaměřením na sbírku etnografických materiálů, z níž se vrátil 7. dubna 1874. Probádal východní okraj pouště Kalahari a navštívil Šošong, hlavní sídlo kmene Bamangwatů. Zpět se vracel podél řeky Limpopo. Třetí expedici vykonal od 2. března 1875 do listopadu 1877, při níž podnikl cestu k řece Zambezi a zpracoval první detailní mapu oblasti Viktoriiných vodopádů. Dorazil až do Šešeke, hlavního sídla kmene Loziů (Bartostů, Maruců), kde se setkal s jejich králem Sipopem. Sipopo byl krutý tyran, ale Holuba si oblíbil a poskytl mu prostředky na plavbu po řece Zambezi. Ta však neskončila příliš šťastně, neboť Holub i s domorodcým doprovodem ztroskotal v peřejích, kde se utopily jeho sbírky, cestovní deníky i několik domorodých veslařů.
Po tomto neúspěchu se Holub rozhodl k návratu. 5. srpna 1879 se vydal na zpáteční cestu do Evropy. Do Prahy s sebou vzal i bečuánskou dívku Bellu. Vrátil se 18. října téhož roku a začal přednášet po celém území Rakouska-Uherska a psát články. Napsal a vydal první knižní popis Viktoriiných vodopádů, vydaný anglicky v Grahamstownu roku 1879. Na Střeleckém ostrově uspořádal velkou výstavu. V letech 1880-1881 vydal cestopis Sedm let v jižní Africe - příhody, výzkumy a lovy na cestách mých od polí diamantových až k řece Zambesi (1872-1879). 2. listopadu 1883 se oženil s osmnáctiletou dívkou Rosou (Růženou) Hofovou (1865-1958), s níž se seznámil ve Vídni.
Díky podpoře veřejnosti i císařského dvora připravoval druhou cestu do Afriky, při níž chtěl z Kapského Města projít celým kontinentem až do Káhiry. V případě komplikací by se obrátil k východu na pobřeží Indického oceánu. Vyplul 22. listopadu 1883 a 22. prosince přistál v Kapském Městě. Provázela jej manželka a šest mužů, které si vybral pomocí konkurzu: Josef Špíral ze Šťáhlav, Antonín Halouska z Rajhradu, Osvald Söllner a Karel Bukač z Vídně, Ignác Leeb z dolnorakouského Harmansdorfu a János Fekete z maďarského Csongrádu. Každý muž z této šestice ovládal alespoň dvě užitečná řemesla. Expedice směřovala z Kapského města přes řeky Oranje a Vaal do dnešní země Bečuánců a Bamangwatů v dnešní Botswaně a dále přes území Loziů (Maruců), Supiů (Mašupiů a Tongů (Matoků) do dnešní Zambie. Na cestě došlo k mnohým nesnázím, jako byl např. úhyn tažných volů po požití jedovatých rostlin, expedice byla poté odkázána pouze na služby domorodých nosičů. Josef Špíral a Karel Bukač zemřeli na malárii nedaleko Viktoriiných vodopádů. Kvůli špatnému zdravotnímu stavu poslal Holub Antonína Halouska domů. V létě roku 1886 Holub opustil území Tongů a vydal se do země bojovných Mašukulumbů (Ilů), kteří nosili zvláštní špičaté účesy. Holub byl prvním Evropanem, který navštívil jejich území. 2. srpna 1886 bojovní Mašukulumbové přepadli Holubův tábor u vesnice Galulongy a zabili Osvalda Söllnera. Zároveň ukradli podstatnou část zásob, zničili sbírky i deníkové záznamy. Holub s manželkou a zbývajícími dvěma pomocníky museli uprchnout zpět na území Tongů. Zde byl Ignác Leeb těžce zraněn levhartem a Holub i jeho manželka vážně onemocněli. V cestě už Holub nemohl pokračovat a musel se vrátit zpět. Koncem září roku 1887 přijel do Čech. Přesto se mu podařilo shromáždit mnoho přírodovědného i etnografického materiálu a poznatků, které byly oceňovány ve vědeckých kruzích u nás, v Německu, Francii a Anglii. Plánoval ještě třetí výpravu do Afriky v roce 1889. Tentokrát měl zamířit na popud Leopolda II. do Belgického Konga. Zdravotní stav mu to již nedovolil.
Vydal knihu Druhá cesta po Africe - Z Kapského Města do země Mašukulumbů. Uspořádal dvě velké výstavy (1891 ve Vídni a 1892 v Praze), které navštívilo 190 000 návštěvníků. Pro nízké vstupné však výstavy skončily finanční ztrátou. Nepodařilo se mu získat prostor pro trvalé umístění svých sbírek (okolo 13 000 předmětů) a začal je po částech rozprodávat nebo je i daroval muzeím, vědeckým institucím a školám. V roce 1894 odjel na dva roky přednášet do USA. V Africe překonal malárii a další tropické nemoci, které se pak projevily na jeho zdravotním stavu v posledních letech života. Zemřel ve Vídni 21. února 1902 v 55 letech a zde je také pohřben.
Manželka Rosa Holubová žila se svou sestrou ve Vídni a několikrát navštívila Československo. V roce 1957 ji ve vídeňském bytě navštívili cestovatelé Miroslav Zikmund a Jiří Hanzelka. Zemřela 28. září 1958 ve věku 93 let a v závěti odkázala zbylé věci po manželovi Holicím.
- Sedm let v Jižní Africe
- Druhá cesta do jižní Afriky - Z Kapského Města do země Mašukulumbů.
