Mažeikiai is first mentioned in written sources in 1335. A chronicler of the Livonian Order wrote about a campaign of the Order, during which the land of Duke Mažeika was devastated. The town started growing rapidly in 1869 when the Libau–Romny Railway connecting Vilnius and Liepāja was constructed. In 1893, the town had 13 shops and 5 alehouses. In 1894 an Orthodox church was built and a synagogue had been founded several years earlier, in 1902 a Catholic church, and in 1906 an Evangelical-Lutheran church. From 1899 to 1918 the town was called Muravyov. In 1939 the population of the town was recorded as 5,618. In 1940 the Soviet Union occupied the town and the following year the Germans occupied the town in August 1941 a mass-killing occurred in which 4,000 Jews from the Mažeikiai district were killed.
In 1980 an oil refinery plant "Mažeikių Nafta" was opened. Today it is one of the largest industrial plants in Lithuania. Its privatisation to Williams, an American energy company, caused many scandals and major disturbances in the Lithuanian government. Williams International facing financial problems sold Mažeikių Nafta to Yukos. After Yukos' bankruptcy, the Lithuanian government and Polish company PKN Orlen signed a sale agreement of Mažeikių Nafta in 2006. Also Yukos International UK B.V. signed a sale agreement with PKN Orlen, selling its Mažeikių Nafta shares to the Polish company. The buyout was finalized on 15 December 2006, with USD 1,492,000,000 being paid by PKN Orlen to Yukos International, and USD 851,828,900.31 to the Lithuanian Government. In 2004, Mažeikių Nafta financed the construction of New church of Saint Francis of Assisi, which cost 650 000 LTL.