Родился 21 марта 1972 года в Астрахани в семье служащих 1 . По национальности русский.
В 1989 году Олег Шеин закончил среднюю школу № 15 с золотой медалью.
В 1989 году вступил в Объединенный фронт трудящихся России (ОФТ) 2 и создал Астраханскую организацию ОФТ.
В 1990 году Шеин стал членом Координационного Совета Объединенного Фронта Трудящихся России.
В 1992 году Шеин был избран в Исполком ОФТ.
3-4 октября 1993 года Олег Шеин участвовал в событиях у Белого дома и телецентра "Останкино" в Москве на стороне Верховного совета 3 .
В 1994 году закончил Астраханский государственный педагогический институт имени С. М. Кирова 4 по специальности “история”.
В 1994 году Шеин был избран в Представительное собрание Астраханской области первого созыва. Занимал пост заместителя председателя Комиссии по природопользованию и природным ресурсам. 5 .
В 1994 - 1995 гг. работал учителем истории в школе села Три Протока Приволжского района Астраханской области.
В 1995 Олег Шеин участвовал в выборах в Государственную Думу Российской Федерации, в составе общефедерального списка блока "Коммунисты — Трудовая Россия — За Советский Союз". В парламент не прошел.
В 1995 году по инициативе О. Шеина в Астраханской области начали создаваться рабочие профсоюзы "Защита" (официальное название - Межрегиональное объединение рабочих профсоюзов "Защита труда").
В 1996 году Шеин был избран сопредседателем межрегионального Объединения рабочих профсоюзов "Защита труда". В течение года профсоюз провел 46 забастовок.
В 1997 году Олег Шеин стал членом президиума координационного совета блока "Коммунисты - Трудовая Россия - За Советский Союз".
26 октября 1997 года О. Шеин был избран депутатом Астраханского областного Представительного собрания второго созыва и стал председателем комиссии областной Думы по законности, правопорядку, нормотворчеству и местному самоуправлению.
С 1999 года стал членом исполкома "Движения за рабочую партию".
В 1999 году был избран депутатом Государственной Думы по Астраханскому одномандатному округу, получив 21% голосов. О. Шеин вошел в состав группы "Регионы России", являлся членом думских комитетов по труду и социальной политике, по проблемам разрешения трудовых споров и конфликтов на предприятиях. В связи с избранием в Госдуму досрочно сложил с себя полномочия депутата областного представительного собрания.
В 2001 году закончил Санкт-Петербургский государственный университет по специальности "Юриспруденция".
В 2001 году в СМИ появилась информация о планах создания левоцентристской "Партии Труда" на базе движения "Вся Россия" и ряда альтернативных профсоюзов, в том числе возглавляемого Шеиным объединения "Защита труда". Учредительный съезд Российской партии труда состоялся в январе 2002 года. Олег Шеин стал ее председателем.
27 февраля 2003 года в центре Астрахани неизвестные напали и избили Олега Шеина.
В августе 2003 года рядом представителей партий и общественных организаций, в том числе и Шеиным, было подписано соглашение о совместной деятельности народно-патриотических сил. Однако в начале осени того же года партия Шеина откололась от блока из-за разногласий в руководстве "Партии Труда". В результате партия и Шеин со своими сторонниками вступили в избирательный блок Глазьева "Родина" 6 .
В октябре 2003 года был вновь избран депутатом Государственной Думы России по Астраханскому одномандатному округу, получив 36 % голосов. Вошел в состав фракции "Родина". Был избран заместителем председателя Комитета по труду и социальной политике.
В апреле 2004 года состоялся учредительный съезд "Партии трудовой солидарности" (ПТС), на котором Шеина избрали ее председателем. В 2005 году "Партия трудовой солидарности" подавала документы на регистрацию, однако не была зарегистрирована из-за своей малочисленности.
В марте 2004 года Олег Шеин победил на выборах депутатов Астраханского областного Представительного Собрания, однако выборы были признаны несостоявшимися ввиду недостаточно высокой явки.
В октябре 2004 года на довыборах депутатов Астраханского областного Представительного Собрания О. Шеин одержал победу. Он был избран заместителем председателя Комиссии по экономической политике, природопользованию и природным ресурсам областной Думы. Возглавил рабочую группу по проверке итогов приватизации.
7 июня 2005 года вступил в партию "Родина". Был членом ее президиума, председателем Совета Астраханского регионального отделения партии.
В феврале 2006 года Шеин был избран членом Президиума партии "Родина".
В октябре 2006 года во время выборов в областную Думу возглавленный О. Шеиным список партии "Родина" получил в Астраханской области 16,1% голосов - лучший результат "Родины" по стране (средний по России - 4,5%) 7 .
28 октября 2006 года в результате объединения партий «Родина», Российская партия пенсионеров и Российская партия жизни была создана партия «Справедливая Россия: Родина / Пенсионеры / Жизнь», в дальнейшем – «Справедливая Россия». Олег Шеин стал лидером регионального отделения партии в Астраханской области.
В сентябре 2007 года О. Шеин выступил одним из организаторов Всероссийского Конгресса жилищного движения, избран сопредседателем Российского Союза жителей.
В декабря 2007 года Шеин вновь стал депутатом Государственной Думы; был избран в составе федерального списка кандидатов, выдвинутого политической партией "Справедливая Россия". Являлся заместителем руководителя фракции "Справедливая Россия" и членом Президиума партии. Был заместителем председателя Комитета ГД по труду и социальной политике, членом Счетной комиссии ГД 8 .
11 октября 2009 года Олег Шеин баллотировался на пост мэра Астрахани, составив конкуренцию действующему на тот момент мэру города, представителю "Единой России" Сергею Боженову и показал максимальный для представителя оппозиции результат - 26% голосов. Победитель, Сергей Боженов тогда заявил: "Я готов предложить своему политическому оппоненту должность руководителя МУП, потом место зама по ЖКХ. А через 5 лет можно вновь попытать удачу" .
12 октября 2009 года Олег Шеин заявил, что победа Боженова стала возможной лишь в результате масштабных фальсификаций и потребовал отмены итогов выборов. Сторонниками "Справедливой России" и Олега Шеина в рамках протеста против итогов выборов мэра был выстроен палаточный городок , который был разобран милицией 13 октября.
В мае 2011 года Олег Шеин выступил с заявлением , в котором прямо обвинил власти Астрахани в том, что за восемь месяцев в центре Астрахани в результате поджогов сгорели 60 многоквартирных домов, при этом погибло 28 человек.
"Сгорели купеческие дома в центре города. Причем, это были именно поджоги. Есть официальное заключение органов пожарного надзора, где сказано, что в 4-5 утра разливали бензин в коридоре дома и потом поджигали" , - констатировал Шеин.
По его словам, "основная проблема Астрахани заключается в прямом сращивании муниципалитета с криминальными кругами" . "Есть ощущение их полной безнаказанности - в городе очень хорошая связка между мэрией и областным судом" , - говорил О. Шеин. Также он отмечал, что пожары в жилых домах в центре города начались после 2005 года, когда мэром Астрахани стал Сергей Боженов.
4 декабря 2011 года Олег Шеин участвовал в выборах в Государственную Думу РФ в составе регионального списка партии "Справедливая Россия" по Астраханской области. Перед выборами О. Шеин дал интервью "Кавказскому узлу".
По итогам выборов в 4 декабря 2011 года Олег Шеин лишился мандата депутата Госдумы РФ, но был избран депутатом Думы Астраханской области пятого созыва. Он возглавил фракцию "эсеров" в областной думе .
4 марта 2012 года Олег Шеин участвовал в выборах мэра Астрахани, на которых, по данным Избиркома, занял второе место, набрав около 30 процентов голосов избирателей. Мэром Астрахани был объявлен Михаил Столяров, которого поддержали более 60 процентов голосовавших .
6 марта Олег Шеин заявил о намерении добиться отмены результатов выборов .
"Мы намерены добиваться отмены результатов выборов мэра Астрахани. На участках, где были установлены КОИБы, у меня было 5,9 тыс. голосов, у исполняющего обязанности мэра Столярова - 5,2 тыс. голосов. Сейчас мы собираем все возможные материалы о нарушениях" , - говорил Олег Шеин.
15 марта началась бессрочная политическая голодовка с требованием отмены результатов выборов мэра и Гордумы Астрахани , в которой приняли участие шесть человек.
17 марта к акции присоединился Олег Шеин , а общее количество голодающих выросло до 12 человек.
"Мы добиваемся перевыборов. Напомню, главная проблема в том, что отметки в бюллетенях на львиной доле избирательных участков не показывали вообще" , - заявил Олег Шеин.
По состоянию на 10 апреля 2012 года Олег Шеин продолжал принимать участие в голодовке . Участники акции высказывали намерения бороться до конца , то есть до отмены итогов выборов мэра Астрахани . Состав участников менялся, некоторые были госпитализированы , другие выбывали по состоянию здоровья , но в то же время к акции постоянно присоединялись и новые участники .
21 апреля в Астрахани состоялась акция в поддержку в поддержку экс-кандидата в мэры города Олега Шеина в рамках которой Шеин заявил, что прекращает голодовку, пояснив, что приурочил это к освобождению активистов , задержанных во время акции 20 апреля.
О. Шеин является автором книг "КПРФ на запасном пути российского капитализма", "Права наемных работников" и других произведений исторической 9 и политической тематики 10 .
Хобби и увлечения Олега Шеина: философия, современная экономика, история (африканистика, Первая мировая война), работа на компьютере 11 .
Семейное положение: Женат (с 2001 года), супруга - гражданка Франции Карин Клеман, доктор социологических наук, директор Института Коллективного действия - информационно-аналитического агентства, работающего в сфере поддержки социальных инициатив.