Atlantsolía var stofnuð 11. Júní 2002 af Brandon C. Rose, Guðmundi Kjærnested og Símoni Kjærnested og hefur félagið frá verið frá upphafi í þeirra eigu.

Fyrsta skref félagsins var að reisa birgðarstöð með þremur tæplega 4 milljón lítra tönkum við Óseyrarbraut í Hafnarfirði og lauk framkvæmdum í júlí 2003.

Fyrsti olíufarmur félagsins kom frá Statoil sumarið 2003. Farmurinn var díselolía og skipagasolía og hófst sala til stórnotenda strax.

Fyrsta bensínstöð fyrirtækisins var opnuð að Kópavogsbraut 115 og fyrsti dísellítrinn var seldur 1. desember 2003 og fyrsti bensínlítrinn 8. janúar 2004. 

Tilkoma Atlantsolíu hleypti sannarlega lífi í samkeppni á eldsneytismarkaðnum en fyrsti bensínlítrinn var seldur á 92,5 kr. sem þá var 2 krónum lægra verð en hjá samkeppnisaðilunum.

Þegar bensínsalan hófst var gert ráð fyrir að fyrstu birgðir myndu duga í 3 vikur en viðtökur fóru fram úr björtustu vonum og dugðu aðeins í 4 daga og varð félagið því bensínlaust í tæpar 3 vikur eftir að fyrstu birgðir kláruðust.

Samkeppnisaðilar brugðust við með því að lækka verð í nágrenni Atlantsolíu en hækkuðu verð um leið og bensínið kláraðist hjá félaginu. Það má því fullyrða að samkeppni á olíumarkaði hafi aukist með tilkomu AO.

Atlantsolía hefur haft það að leiðarljósi að bjóða ávallt samkeppnishæft verð á eldsneyti, gott aðgengi að bensínstöðvum og einfaldleika í þjónustu.

AO var fyrst íslenskra olíufélaga til að lækka verð og afnema afslætti sem svar við aukinni samkeppni við Costco á bensínstöðinni við Kaplakrika í Hafnarfirði vorið 2017. Þessi viðleitni AO í virkri samkeppni fékk síðar viðurnefnið Bensínsprengjan og undir þeim hatti eru nú 5 bensínstöðvar félagsins, 3 á höfðuðborgarsvæðinu, Akureyri og Selfossi.

Það var stefna Atlantsolíu frá upphafi að reka eingöngu sjálfsafgreiðslustöðvar og var það trú stofnenda að þar væri framtíðin í sölu eldsneytis auk þess sem áhersla var lögð á að einfalda eldsneytiskaup fyrir viðskiptavini.

Þannig var dælulykillinn kynntur á íslenskum markaði árið 2006 og viðtökurnar voru frammúrskarandi. Í kjölfarið voru fleiri lausnir þróaðar til að einfalda eldsneytisviðskiptin og var AO með þeim fyrstu til að bjóða upp á tölvupóstkvittanir og aðgang að þjónustusvæði dælulykils.

Árið 2024 kynnir AO smáforrit/app - dælulykilinn í símann, fyrst olíufélaga og svarar þar með kalli viðskiptavina um aukinn einfaldleika og þægindi við eldsneytiskaupin.

Í dag rekur Atlantsolía 25 sjálfsafgreiðslustöðvar, 18 á höfuðborgarsvæðinu og Suðurnesjum og 7 stöðvar á landsbyggðinni.

AO hefur fest sig í vitund og ímynd sem "litla óháða" olíufélagið á markaðinum.

Lykilorð í markaðstarfi félagsins eru: einfalt – ódýrt – skemmtilegt.

Út frá þeim gildum, með snjöllum lausnum og vel útfærðum aðgerðum sem hreyfa við neytendanum hefur AO tekist að skapa sérstöðu og aðgreiningu á eldsneytismarkaði.

Félagið hefur hlotið ýmsar viðurkenningar í markaðsmálum:

• Áran - fyrir árangursríkustu auglýsingaherferðina 2022
• 6 Lúðrar - ÍMARK verðlaunin á árunum 2018-2023 
• Tilnefning sem Markaðsfyrirtæki ársins 2022
• Tilnefning Besta íslenska vörumerkið 2023

AO hefur ennfremur verið Frammúrskarandi fyrirtæki í rekstri skv. Creditinfo 2019-2023.