Родился 8 ноября 1960 года, в городе Серпухов, Московской области, в семье военного инженера и врача. После окончания общеобразовательной и музыкальной школ (1977 год) поступил в Московское театральное училище им.М.Щепкина, на курс Н.Н. Афонина. Со своими однокурсниками создавал номера, поставил спектакль, капустники.

Дебют в кино состоялся в 1980 году в картине Сурена Шахбазяна «Жду и надеюсь». Затем последовали фильмы «Родня» Никиты Михалкова и «Полёты во сне и наяву» Романа Балаяна, где Олег Меньшиков обратил на себя внимание даже в эпизодических ролях.

В 1981 году после окончания театрального училища поступил в Малый театр. Учась на последнем курсе Театрального училища был приглашён Михаилом Козаковым на роль Костика в картине «Покровские ворота». На экран этот фильм вышел в 1982 году и именно эта роль принесла актёру популярность и любовь зрителей.

После роли Костика последовал ряд разноплановых ролей, в том числе в фильмах «Капитан Фракасс» (1984), «Володя большой, Володя маленький» (1985), «Мой любимый клоун» (1986), «Моонзунд» (1987). Роль в последнем принесла актёру Серебряную медаль им.А.П. Довженко.

Через год работы в Малом театре, не принесшей ярких ролей, Олег Меньшиков, отбывая воинскую обязанность, играет в Центральном театре Советской Армии. Одна из самых ярких ролей сыгранных им в этом театре это роль Ганечки в спектакле по роману Федора Михайловича Достоевского «Идиот».

В 1985-1989 - актер Московского драматического театра им.М.Ермоловой, где наиболее заметными ролями стали роли в спектаклях «Спортивные сцены 81 года» и «Второй год свободы», (реж. Валерий Фокин).

За роль римского императора Калигулы в одноимённом легендарном спектакле Петра Фоменко, поставленном в 1990 году, Олег Меньшиков получил премию и диплом Фестиваля «Московские сезоны».

В 1991 году Олег Меньшиков сыграл роль Сергея Есенина в спектакле «Когда она танцевала» Лондонского театра «Глобус», с Ванессой Редгрейв в роли Айседоры Дункан. В 1992 году актер был удостоен за эту роль премии имени Лоуренса Оливье Британской Академии искусств. Затем там же актёр участвовал в спектакле по Н.В. Гоголю «Игроки» в роли Ихарева.

Следующей театральной ролью, также имевшей большой успех, стала роль великого русского танцовщика Вацлава Нижинского в спектакле «Нижинский» (1993 год, антреприза «Богис»), где он также выступил и в качестве режиссёра. А годом позже он снова играл Есенина в спектакле «Когда она танцевала», но уже в постановке парижского Комеди Франсез на Елисейских полях.

Продолжая сниматься в кино, сыграв главную роль в фильме Александра Хвана «Дюба-дюба» (1992), Олег Меньшиков в 1994 году снялся в фильме Никиты Михалкова «Утомлённые солнцем». Роль в фильме-лауреате американской премии «Оскар» (1994) стала одной из самый ярких в творческой биографии актёра и принесла ему несколько премий. Следующая роль в фильме режиссера Сергея Бодрова-старшего «Кавказский пленник» (1996) была также отмечена наградами. В 1998 году Олег Меньшиков вновь снимается у Никиты Михалкова в фильме «Сибирский цирюльник», за работу в котором актёра удостаивают Государственной премии России.

Следующей ролью в кино стала роль в российско-французском фильме режиссера Режиса Варнье «Восток-Запад» (1999), номинированном на премию «Оскар» в категории «лучший иностранный фильм».

В 1995 году Олег Меньшиков организовал антрепризу «Театральное товарищество 814», где в качестве постановщика и актёра создал спектакли «Горе от ума» (1995), «Кухня» (2000), «Игроки» (2001) и сыграл главную роль в постановке К. Серебренникова «Демон» (2003).

В 2001 году Меньшиков учредил премию для российских театральных критиков - «Лучший критик сезона» им. А. Кугеля, в жюри которой входят актёры и режиссёры Москвы, Петербурга, Воронежа.

Олег Меньшиков входит в постоянный состав независимого жюри премии в области литературы и искусства «Триумф».

В 2003 году Олег Меньшиков снялся в английском сериале «Главный подозреваемый».

За роль в фильме «Сибирский цирюльник» (1999г.) - Государственная премия России в области киноискусства.

В 2003 году за большие заслуги в области искусства Указом Президента РФ Меньшикову Олегу Евгеньевичу присвоено почетное звание "Народный артист Российской Федерации".

В 2004 году Олег Меньшиков получил одну из главных французских наград в области искусства - правительственный орден "Академические пальмы".

В 2005 году женился на актрисе Анастасии Черновой.

В начале 2008 года поставил свой первый моноспектакль «1900» на сцене Театра им. Моссовета в рамках фестиваля «Черешневый лес».