Mýty vypráví, že ostrov objevily a osídlily múzy.
Podle starých bájí však byl první král na ostrově Makaras, syn Boha slunce Helia. Tento bájný král měl pět dcer: Mytilene, Methymna, Issa, Antissa a Arsine a čtyři syny: Eressos, Kydrolaos, Neandros a Leukippos. Podle nich jsou pojmenovaná nejdůležitější města ostrova. Jeden Makarasův zeť se jmenoval Lesbos, syn antického hrdiny Lapithose a po něm je pojmenovaný celý ostrov.
Pravděpodobně byl ostrov osídlen ve 4 tisíciletí před Kristem. Slepý antický básník Homér zmiňuje ostrov v obou svých eposech Ilias i Odysea. Podle Homéra byl Lesbos místem, kde bájní hrdinové Achilles a Ajax pohřbili dalšího slavného bojovníka Trójské války, Palamida. Vykopávky dokazují, že na ostrově byla civilizace paralelně s civilizací Mykénskou a Trójskou.
Okolo jedenáctého století před Kristem, asi 60 let po pádu Tróje byly na ostrově založeny aiolské kolonie. Město Mytilény začalo vzkvétat, ekonomicky se rozvíjet a osídlovat pobřeží Malé Asie naproti. Asijské pobřeží pojmenovali Mytilénské pobřeží a protože to byla oblast blízko Achillova hrobu, založili město Achilleion.
V šestém století se stal Lesbos centrem obchodu s Egyptem. Později mezi lety 492 až 479 př.n.l. se dostal Lesbos pod nadvládu Peršanů. V Peloponéské válce se ho několikrát zmocnili jak Athény tak Sparta. Později byli spojencem Alexandra Velikého a po jeho smrti spadal pod vládu Ptolemaia.
Od roku 88 př.n.l. byl Lesbos pod římskou nadvládou. V tomto období navštívil ostrov např. Julius Caesar, Cicero, Pompeius nebo svatý Pavel. V roce 70 n.l. byl ostrov začleněn císařem Vespasiánem do Říše římské. Po rozdělení římského impéria připadl Lesbos říši Východořímské (Byzantské). Až do 14. století patřil ostrov různým byzantským vládcům, ale nikdo se o něj příliš nestaral několikrát byl v tomto období Lesbos zpustošen nájezdy Maurů, Benátčanů, nebo křižáků.
V roce 1354 ostrov dostal darem janovský šlechtic Francesco Gattelusi. Ten vládl do roku 1376. Během své vlády zrekonstruoval hrad v Mytilény. Po něm na ostrově vládli jeho synové. V roce 1401 byl ostrov poničen zemětřesením. Roku 1445 ostrov vyplenil Bulgar Baldaoglou a někdejší ekonomicky velmi silné město Kalloni srovnal se zemí.
V roce 1462 Mohamed II. Dobyvatel zaútočil na Mytilény. V září tohoto roku napadl město od moře, ve městě bylo na 20 000 obyvatel, z toho 15 000 civilistů a 5 000 vojáků. Během prvních dvou dnů sultán povraždil velké množství civilistů a poničil skoro celou lesboskou námořní flotilu. Turkové se pokusili obsadit hrad, ale neúspěšně. Obyvatelé na nepřátele valili kameny z hradeb a ti byli nuceni se stáhnout s těžkými ztrátami. Čtvrtého dne obléhání se místní obyvatelé vzpamatovali a zatlačili Turky daleko od hradeb města. Dalšího dne ale Turci odpověděli silným útokem, těžce poničili hrad a opevnění města. Tehdejší vládce ostrova Nicola Gattelusi, když viděl, že další odpor je beznadějný, začal vyjednávat s dobyvatelem pašou Mahmutem. Podmínky byly nechat Gattelusimu a jeho rodině část ostrova na dožití, nerabovat domy a kostely a ponechat místnímu obyvatelstvu jejich náboženství.14. října se ostrov oficiálně stal majetkem Sultána Mohameda II. Začala turecká okupace. První věc, kterou Sultán udělal, byla, že vybral 800 krásných a silných chlapců a dívek a poslal je do svého harému v Konstantinopoli. Město bylo vydrancováno a z původních 100 000 bohatých obyvatel na ostrově z časů Gattelusiho, zůstalo 30 000 negramotných chudáků. Velká část byla prodána do otroctví a část se odstěhovala dobrovolně či nedobrovolně do Konstantinopoli. Zbylí obyvatelé byli donuceni vzdát se křesťanství a Gattelusi a jeho rodina byli pověšeni. Odpor Řeků byl z počátku slabý, ale postupem času se začaly formovat tajné školy v kostelech a klášterech a stejně tak jako ve zbytku okupovaného Řecka i tady duchovenstvo udržovalo naději na osvobození.
V průběhu turecké okupace byl Lesbos vypleněn Benátčany a Rusy a bylo to místo exilu pro turecké vojevůdce, kteří se jakkoliv znelíbili sultánovi.
V roce 1677 Turkové opravili hrad v Mytilény a v roce 1757 postavili nový hrad v Sibir, aby chránili východní část ostrova před častými nájezdy.
Během Rusko-turecké války mezi lety 1768-1774 nařídil Mohamed, aby byl ostrov Lesbos v první obranné linii. Mnoho těch, kteří doprovázeli Rusy do války, proto plenili a rabovali ostrov, jako odplatu za turecké zabíjení křesťanů. Válka skončila dohodou Kuchuk - Kainarji a na ostrově začala po 2 000 letech opět doba rozkvětu. Tato mírová dohoda povolila svobodu vyznání řeckým křesťanům a Rusům dala právo vystupovat jménem řeckých kostelů, které byly v té době silným a jediným pojítkem mezi řeckými obyvateli. Církevní cestou se šířila i myšlenka na vzpouru mezi jednotlivými řeckými koloniemi.
Vzpoury začali nejrůznějšími útoky. V roce 1821 Dimitrios Papanikolis vyhodil do vzduchu tureckou fregatu ve vodách okolo Eressosu, Turkové na oplátku povraždili mnoho křesťanů. O tři roky později Turci krvavě potlačili povstání v Mytilény. V roce 1867 ostrov postihlo silné zemětřesení, tisíce lidí zahynulo pod troskami a město Mytilény bylo velmi poničeno.
8. listopadu 1912 bylo Mytilény osvobozeno řeckou námořní flotilou. Oficiálně byl Lesbos připojen k Řecku v roce 1914 dohodou mezi Londýnem a Athénami. Fakticky začali ostrov spravovat Řekové až po roce 1923, kdy zem opustili poslední Turci.
Během druhé světové války ostrov okupovali Němci a to od roku 1941 do roku 1944.
Dnes ostrov patří k Řecku, oficiálně Řecká republika (Elliniki Dhimokratia) a z Lesbu se pomalu stává velmi oblíbená turistická oblast.
Z názvu ostrova byl později odvozen název pro homosexuální vztah žen a to protože se tady narodila a tvořila jedna z mála známých básnířek starověku a jedna z nejvýznamnějších představitelek řecké lyriky vůbec - Sapfó. Narodila se někdy mezi roky 630 a 612 před n.l. Byla to aristokratka, která se provdala za prosperujícího obchodníka, se kterým měla dceru. Studovala umění na svém domovském ostrově Lesbos. Sapfó se tady ale neusídlila natrvalo - hodně cestovala a načas byla kvůli aktivitám své rodiny donucena k odchodu do exilu v Syrakusách, kde jí mimochodem jako výraz úcty vztyčili sochu. Na Sicílii pobývala snad v letech 603 - 595 před n.l.
Sapfó byla již ve své době nazývána lyričkou, což však nemělo onen básnický podtext dnešních časů. Sapfó se totiž během přednesu své poezie improvizovaně doprovázela na lyru. Patřila mezi vůbec první, kdo psal v první osobě o svých pocitech včetně lásky. Její projev byl údajně velmi citový. Psala hlavně básně s mileneckou tematikou, přičemž si poměrně často vybírala za terč svého básnického obdivu své žačky; mnohým dokonce složila svatební píseň, což byl v Řecku poměrně dosti oblíbený žánr. Je třeba si ale uvědomit, že pověsti o lesbických stycích mezi Sapfó a jejími následovatelkami jsou pozdějšího data a nemusejí se zdaleka zakládat na pravdě. Přesto však díky Sapfó máme dvě nejčastější pojmenování pro ženskou homosexuální lásku - lesbická a sapfická. Inu, historie nebývá vždy spravedlivá. Je tedy třeba dodat, že podle řecké tradice skončila básnířka tak, že skočila ze skály, protože nemohla získat lásku mladíka Faóna. Tuto verzi smrti básnířky sepsal římský básník a v jistém smyslu Sapfin nástupce Ovidius.