Maine var byggt u.þ.b. 20 ættkvíslum algonquian-indíána (abenaki eða wabanaki; dögunarfólkið), þegar evrópumenn hófu innreið sína.  Penobscot- og passamaquoddy-indíánar eru einu ættkvíslirnar, sem eru eftir.  Franskir trúboðar snéru mörgum þeirra til katólskrar trúar á 17. öld og þeir börðust með Frökkum gegn Bretum.

Nýlendutíminn og uppreisnir.  John Cabot kannaði hluta Nýja-Englands einni öld áður en Frakkar komu til sögunnar og James I, Englandskonungur, fól Plymouth-félaginu landnám þess árið 1606.  Ári síðar stofnaði það til byggðar við ósa Kennebec-árinnar á Sagadahoc-skaga en hún entist aðeins í eitt ár.  Franskt landnám á St Croix-eyju og Mount Desert-eyju mistókst einnig.

Árið 1620 fékk Sir Ferdinando Gorges landið milli Merrimack- og Kennebec-ánna til eignar úr hendi Englandskonungs en hann gerði lítið til nýtingar þess.  Árið 1658 tryggði Massachusetts sér forræði Maine og árið 1691 varð svæðið hluti af því.

Maine var einkum nýtt sem veiðisvæði (skinnakaupmenn) og skógarhöggs fyrir sjálfstæðisstríðið, þótt eitthvað væri um landsölu.  Í stríðinu komu Bretar upp herbúðum í grennd við núverandi Castine við Penobscot-fjörð.  Penobscot-leiðangurinn (1779), sem var sendur frá Massachusetts til að hrekja þá brott, mistókst herfilega.

Sjálfstæði.  Árið 1785 hófust aðgerðir til aðskilnaðar frá Massachusetts.  Aðstandendur þeirra höfðu ekki erindi sem erfiði fyrr en 1816, þegar aðskilnaðarhreyfingin fékk almenning til liðs við sig   Þremur árum síðar, þegar þing Massachusetts samþykkti aðskilnaðarlög, var haldið stjórnarskrárþing í Portland.  Maine sótti um aðild að BNA í desember 1819 og var samþykkt sem 23 fylkið árið 1820.  Næstu árin var fylkið í sviðsljósinu vegna forystuhlutverks sins í bindindismálum og setningu bannlaga 1851.

Aðeins helmingur lands í Maine var numinn, þegar fylkið fékk sjálfstæði og meirihluti hans var ókannaður.  Deilur spruttu upp vegna markanna milli fylkisins og Nýju-Brúnsvíkur í Kanada.  Skömmu fyrir 1840 reyndu stjórnvöld beggja landa að ná yfirráðum á umdeilda svæðinu, sem er nú Aroostook-sýsla.  Blóðugum átökum lauk með íhlutun Bandaríkjahers undir stjórn Winfield Scott, hershöfðingja, og samið var um landamærin (Webster-Ashburton 1842).

Þjóðfélagsbreytingar.  Fyrir borgara/þrælastríðið dafnaði efnahagur Maine vegna mikils útflutnings timburs og íss til matvælaflutninga.  Kalk- og granítnám, vefnaður, sjávarútvegur og skipasmíðar hófust í smáum stíl í fyrstu.  Samgöngur voru bættar með lagningu járnbrauta.  Að stríðinu loknu olli framleiðsla stálskipa og brottflutningur vefnaðariðnaðarins efnahagslægð.  Meiri áherzla var lögð á framleiðslu pappírs og trjákvoðu, sem varð að stóriðnaði á árunum 1880-90.

Fyrri hluta 20. aldar var fylkið eitt höfuðvígja lýðveldissinna.  Um miðjan sjötta áratuginn óx fylgi demókrata með kjöri Edmund Muskie til fylkisstjóraembættisins í tvö kjörtímabil.  Hann vann sér hylli sem þingmaður fylkisins í öldungadeild sambandsþingsins og síðar innanríkisráðherra í stjórn Jimmy Carters forseta.  Annar áberandi demókrati frá Main, George Mitchell, var kjörinn forseti öldungadeildar sambandsþingsins 1988.

Fátækt var útbreidd eftir síðari heimsstyrjöldina.  Orku- og umhverfismál ollu miklum deilum á áttunda og níunda áratugnum, þegar hópar borgara reyndu að fá rekstrarleyfi eina kjarnorkuvers fylkisins afnumið.  Efnahagur Maine blómstraði á níunda áratugnum.  Þá færðist fylkið úr 39. í 21. sæti á listanum yfir árlegar tekjur einstaklinga.