1964 m. buvusiosios Tarybų Sąjungos valstybinis Naftos ir chemijos komitetas pradėjo svarstyti naftos perdirbimo įmonės Lietuvoje idėją.
1966 m. pradėtas naftos perdirbimo įmonės Lietuvoje projektavimas. Įmonei statyti vieta buvo parinkta netoli Jurbarko.
1966 m. per Lietuvos teritoriją pradėti tiesti naftos transportavimo vamzdynai.
1968 m. dirbti pradėjo naftotiekio Polockas–Ventspils Biržų naftos perpumpavimo stotis. Biržuose pradėjo veikti naftos tarnsportavimo įmones „Družba“ padalinys, kuris aptarnavo ir vamzdynų atšaką Latvijoje.
1970 m. darbą pradėjo tarpinė naftos perpumpavimo stotis Biržų rajone, Stačkūnų kaime.
1970 m. Lietuvos valdžios institucijos kreipėsi į Maskvos valstybines institucijas prašydamos įmonės statybą perkelti prie Mažeikių. Galutinė statybos vieta buvo patvirtinta 1970 m. birželio 24 d.
1971 m. geologai baigė įmonei numatytos teritorijos tyrimus ir rudenį pradėta ruošti teritoriją statyboms: buvo kertami miškai, tiesiami keliai ir geležinkeliai.
1972 m. pradėta statyti Mažeikių naftos perdirbimo įmonė.
Naftos perdirbimo įmonės pirmosios eilės statyboms panaudota: 1500 tonų plieno konstrukcijų, 2000 km vamzdžių, 20000 tonų betono.
1979 m. baigtas statyti naftotiekis Polockas–Biržai–Mažeikiai. Naftotiekio ilgis Lietuvos teritorijoje 225 km.
1980 m. pradėtas eksploatuoti pirmasis pirminio naftos perdirbimo įrenginys LK–1. Pradėtas eksploatuoti naftotiekis Polockas–Biržai–Mažeikiai.
1982 m. pastatytas bitumo gamybos įrenginys
1984 m. pastatytas ir pradėtas eksploatuoti analogiškas antrasis pirminio naftos perdirbimo įrenginys LK–2.
1989 m. pastatytas mazuto giluminio perdirbimo įrenginys KT–1/1.
1992 m. atsiskyrus nuo „Družbos“ įkurta valstybinė naftos transportavimo įmonė „Naftotiekis“.
1993 m. valstybinė naftos perdirbimo įmonė „Nafta“ pradėjo projektuoti Būtingės terminalą.
1995 m. įkurta akcinė bendrovė „Būtingės nafta“.
1995 m. įkurta specialiosios paskirties akcinė bendrovė „Naftotiekis“, tais pačiais metais vėl reorganizuota į akcinę bendrovę.
1995 m. valstybinė naftos perdirbimo įmonė „Nafta“ reorganizuota į akcinę bendrovę „Mažeikių nafta“, kurios 90 proc. akcijų priklausė valstybei.
1995 m. pradėta Būtingės terminalo statyba.
1998 m. akcinės bendrovės „Mažeikių nafta“, „Būtingės nafta“ ir „Naftotiekis“ reorganizuotos, prijungiant bendroves „Būtingės nafta“ ir „Naftotiekis“ prie toliau tęsiančios veiklą akcinės bendrovės „Mažeikių nafta“.
1999 m. baigta Būtingės terminalo statyba, 1999 m. liepos 22 d. Būtingės terminale pripildytas pirmasis tanklaivis.
1999 m. spalio 29 d. 33 proc. „Mažeikių naftos“ akcijų įsigijo JAV bendrovė „Williams International“. Šiai bendrovei perduotas įmonės valdymas.
2000 m. įmonė pradėta modernizuoti.
2002 m. birželio 18 d. Rusijos naftos kompanija „Yukos“, „Williams“ ir Lietuvos Vyriausybė pasirašė Akcininkų ir Investicijų sutartis dėl 150 mln. JAV dolerių vertės sandorio. Remiantis šiomis sutartimis, tiek „Williams International“, tiek „Yukos“ priklausė po 26,85 proc. „Mažeikių naftos“ akcijų, LR Vyriausybei — 40,66 proc. akcijų. Be to, „Mažeikių nafta“ ir „Yukos“ pasirašė 10 metų sutartį dėl naftos tiekimo.
2002 m. rugsėjo 19 d. „Yukos“ įsigijo iš „Williams International Company“ papildomą 26,85 proc. akcijų paketą ir su tuo susijusias teises „Mažeikių naftoje“ bei prisiėmė visas su šiuo akcijų paketu susijusias „Williams International“ teises ir įsipareigojimus.
2003 m. pradžioje įsteigta dukterinė įmonė UAB „Mažeikių naftos“ prekybos namai, kuri prekiauja „Mažeikių naftos“ produkcija.
2003 m. rugsėjį baigtas pirmasis įmonės modernizacijos etapas. Pradėtas eksploatuoti izomerizacijos įrenginys.
2004 m. pradėti antrojo modernizacijos etapo darbai. Pradėta eksploatuoti šviesiųjų naftos produktų uždaro pylimo į geležinkelio cisternas estakada.
2005 m. pradėta benzino nusierinimo įrenginio statyba.
2005 m. bendrovė įsigijo AB Mažeikių elektrinės kontrolinį akcijų paketą.
2006 m. atidarytas „Mažeikių naftos“ šiuolaikiškas naftos produktų pylimo į autotransportą terminalas Juodeikiuose.
2006 m. „Mažeikių naftos“ pagrindiniu akcininku tapo Lenkijos koncernas PKN ORLEN.
2007 m. rugpjūčio mėnesį pradėtas eksploatuoti katalizinio krekingo benzino nusierinimo įrenginys.
2009 m. biželio mėn. iškilmingai atidarytas naujasis vandenilio gamybos įrenginys.
2009 m rugsėjo 1 d. Akcinė bendrovė „Mažeikių nafta“ tapo Akcine bendrove „ORLEN Lietuva“.
2013 m. balandžio mėn. iškilmingai atidarytas naujas sieros degazavimo ir granuliavimo įrenginys.
2014 m. vasario mėnesį pradėtas eksploatuoti visbrekingo likučio vakuuminės rektifikacijos įrenginys.
2018 m. sausio mėnesį pradėtas eksploatuoti 6-as naftos rezervuaras Būtingėje.
2019 m. sumontuotas ir paleistas elektrostatinis filtras katalizinio krekingo įrenginyje.