Höldur ehf. var stofnað árið 1974. Stofnendur fyrirtækisins voru bræðurnir Birgir, Skúli og Vilhelm Ágústsynir en upphaf að rekstrinum má þó rekja mun lengra aftur í tímann, eða til ársins 1966 þegar Skúli keypti sér fimm bíla og hóf að leigja þá út. Ári seinna keyptu bræður hans þeir Birgir og Vilhelm sína þrjá bílana hvor og voru þeir bræður þá komnir með 11 bíla í leigu sumarið 1967 og yfirtóku þá bílaleiguna Prinz á Akureyri. Svona hlóð þetta smám saman utan á sig og árið 1970 voru bílarnir orðnir um 20. Það ár keyptu þeir Ísbúðina, lítinn söluturn við Kaupvangsstræti, og byggðu verkstæðisskúr við Kaldbaksgötu til að gera við bílana. Á þessum árum voru bræðurnir allir í fastri vinnu annarsstaðar og rekstur bílaleigunnar var aukavinna. Árið 1971 réðu þeir síðan sína fyrstu starfsmenn til starfa fyrir sig. Í desember 1973 keyptu þeir húsnæði Bílaþjónustunnar h.f. að Tryggvabraut 14 þar sem höfuðstöðvar fyrirtækisins voru lengi vel. Þar settu þeir upp afgreiðslu fyrir bílaleiguna, komu sér upp þvottaaðstöðu og opnuðu dekkjaverkstæði. Um svipað leiti tóku þeir við rekstri þriggja bensínstöðva og Nesta af Olíufélaginu.
Var nú svo komið að ekki var lengur unnt að reka fyrirtækið í aukavinnu. Þann 1. apríl 1974 var fyrirtækið Höldur s.f. stofnað, og tók þá yfir allan þann rekstur sem bræðurnir voru búnir að koma sér í. Við stofnun fyrirtækisins voru bílaleigubílarnir orðnir 40, og starfsmenn þess hátt í 40, flestir í tengslum við bensínstöðvarnar. Árið 1976 keyptu þeir litla flugvél til að flytja viðgerðarmenn á þá staði þar sem bílar áttu til að bila, og var það fyrsti vísir að flugrekstri þeirra. Ári síðar, eða 1.apríl 1977 stofnuðu þeir svo útibú fyrir bílaleiguna í Reykjavík og sá Baldur elsti bróðirinn um rekstur þar allt fram til ársins 2003. Í kjölfarið fylgdu útibú víða um land og eru þau nú orðin fjölmörg. Árið 1978 var gamli verkstæðisskúrinn orðinn of lítill og keyptu þeir þá 300 fm. húsnæði við Fjölnisgötu 2a og fluttu þangað allar bílaviðgerðir. Sama ár keyptu þeir aðra flugvél. Tveimur árum síðar, eða árið 1980 tóku bræðurnir við umboði fyrir sölu nýrra bíla frá Heklu hf og tók fimmti bróðirinn Eyjólfur við taumunum þar. Sama ár opnuðu þeir nýtt verkstæði og varahlutaverslun og um mitt ár 1980 tóku þeir við umboði fyrir alþjóðlegu bílaleiguna Inter-Rent á Íslandi. Árið 1981 seldu þeir aðra flugvélina og keyptu 8 sæta skrúfuþotu vegna aukinna umsvifa í flugrekstri sínum. Árið 1986 var svo tekið í notkun nýtt þjónustuverkstæði að Draupnisgötu 1 í stóru og glæsilegu húsnæði. Árið 1988 voru opnaðar tvær nýjar bensínstöðvar og sú þriðja gerð upp að miklu leiti. Árið 1989 keypti fyrirtækið flugskólann Flugtak í Reykjavík og árið 1992 stofnaði Höldur ásamt fleirum flugfélagið Íslandsflug. Árið 1992 keypti Höldur kjúklingastaðinn Crown Chicken á Akureyri og seldi hann aftur árið 2000. Árið 1995 var byggt við skrifstofuhúsnæði fyrirtækisins að Tryggvabraut 12, og bensín og veitingasalan á sama stað stækkuð verulega. Þá seldi fyrirtækið bílaleiguverkstæðishúsnæðið að Fjölnisgötu 2a en keypti í staðinn svokallað Hekluhúsnæði á Gleráreyrum og hefur flutt þangað bílaleiguverkstæðið. Einnig er þar lager fyrir Esso nestin og ýmislegt fleira. Sama ár opnaði fyrirtækið verslunina 66 Norður að Glerárgötu í samvinnu við samnefnt fyrirtæki í Reykjavík. Sjóklæðagerðin í Reykjavík keypti síðan rekstur verslunarinnar árið 2000. Árið 1996 keypti Höldur Glerhúsið við Hafnarstræti þar sem var opnuð verslun og veitingasala í samvinnu við Blómaval í Reykjavík. Höldur ehf átti helming í þeirri verslun en seldi sinn hluta í rekstrinum árið 1998 og leigði húsið út eftir það en það hefur nú verið selt. Árið 2000 seldi Höldur Kjúklingastaðinn og 66°Norður verslunina og var tilgangurinn með þeirri sölu sá að stjórnendur fyrirtækisins gætu einbeitt sér betur að grunnþáttum þess þar sem fyrirtækið hafði vaxið mjög árin á undan.
Í apríl 2003 skipti fyrirtækið um eigendur. Skúli, Vilhelm og Birgir seldu félagið til nokkurra lykilstarfsmanna sinna. Í dag eru stærstu eigendurnir Steingrímur Birgisson, Bergþór Karlsson og Baldvin Birgisson. Í maí 2003 seldi Höldur veitinga og bensínstöðvarekstur sinn og var það í samræmi við stefnu nýrra eigenda sem er að einbeita sér að rekstri bílaleigu og bílaþjónustu. Í júní opnaði fyrirtækið nýja og glæsilega bílasölu að Þórsstíg 2 og sameinaði þar undir einu þaki bílasölu nýrra og notaðra bíla sem fram til þess tíma hafði verið tvískipt.
Í dag rekur Höldur ehf. Bílaleigu Akureyrar, stærstu bílaleigu landsins með fjölda bíla í rekstri og afgreiðslustöðvar víðsvegar um landið. Á Akureyri rekur fyrirtækið öfluga bílaþjónustu, má þar nefna vel búið dekkjaverkstæði ásamt bílaþvottastöð við Glerártorg, bílasölu með nýja og notaða bíla að Þórsstíg 2 ásamt nýlegu og glæsilegu bíla og- tjónaviðgerðaverkstæði í 2300 fermetra húsnæði að Þórsstíg 4.
Um 200 starfsmenn starfa að jafnaði hjá fyrirtækinu í dag.