Олег Евгеньевич Меньшиков родился 8 ноября 1960 г. в подмосковном Серпухове в семье военного инженера и врача-невропатолога. Вскоре семья получила квартиру в Москве – две комнаты в обычной хрущевке на четверых (отец, мать, дедушка и Олег). Мальчик увлекался музыкой, учился игре на скрипке. А еще полюбил театр, особенно музыкальный, и раз в две недели непременно посещал Театр оперетты. В старших классах и сам начал ставить небольшие музыкальные спектакли, в которых был и режиссером, и актером. Окончив музыкальную школу, играл в оркестре юных скрипачей Москвы. Но всерьез связывать жизнь с музыкой Олег не стал: тяга к сцене победила безоговорочно, хотя родители и не были в восторге от его выбора.
Экзамены Меньшиков решил держать в знаменитую «Щепку» – Высшее театральное училище имени Щепкина. «Олег выделился сразу: умный, очень живой, весь какой-то мажорный мальчик, – вспоминал педагог, впоследствии ректор училища Николай Афонин. – Мы его взяли на заметку Советовали Олегу, что читать на следующих турах. Могу признаться по прошествии времени, что стали тогда его болельщиками. Он того заслуживал. Прошел все испытания без сучка и задоринки». Также легко и задорно Меньшиков и учился. Однокурсникам он запомнился как живое воплощение таланта, творческой энергии, юмора. По свидетельству многих, таких гениальных «капустников», как при Меньшикове, в «Щепке» не бывало ни до, ни после него.
В студенческие годы Олег начал сниматься в кино. В 1980-м он дебютировал главной ролью партизана Шурки Доминиани в фильме С. Шахбазяна и Р. Балаяна «Жду и надеюсь». А практически одновременно получил приглашение от Никиты Михалкова сыграть эпизод в «Родне» с Нонной Мордюковой. Правда, там по сюжету Олега брили наголо. Но Роман Балаян, искренне желавший «продвинуть» Меньшикова в мире кино и понимавший, что даже эпизод в фильме Михалкова будет для Олега полезным, нашел выход: для актера сделали парик и досняли его уже в нем. Снимался Меньшиков и в следующем фильме Р. Балаяна – «Полеты во сне и наяву», где главной звездой был Олег Янковский. И зрители сразу же заметили юного артиста, который нисколько не терялся на фоне признанных знаменитостей.
Прославил Меньшикова-киноактера фильм М. Козакова «Покровские ворота» (1982). Задумывавшаяся как незамысловатый водевиль из жизни москвичей 1950-х, эта экранизация пьесы Леонида Зорина стала подлинным гимном «старой» советской Москве и была мгновенно разобрана на цитаты. На экране царили великолепные Хоботов (А. Равикович) и его бывшая супруга (И. Ульянова), Савва Игнатьевич (В. Борцов), Велюров (Л. Броневой), Людочка (Е. Коренева) и Света (Т. Догилева)… А объединял всех этих разных людей в нечто целое, комментировал их действия, фонтанировал юмором, устраивал их судьбы, не забывая при этом и о себе, пел, острил и смеялся обаятельный Костик Ромин – Олег Меньшиков. Этот персонаж и по сей день остается одним из самых привлекательных героев отечественного киноэкрана. А появился Меньшиков в фильме благодаря жене режиссера, которая увидела Олега в его дебютной картине «Жду и надеюсь» и порекомендовала мужу обратить на него внимание. Правда, Олег уже был утвержден на роль у Юлия Райзмана, но после того как сценарист «Покровских ворот» Леонид Зорин написал режиссеру письмо, где подробно объяснил, почему без Олега фильма не будет, Райзман благородно «подарил» Меньшикова Козакову. Позже Михаил Козаков называл актера «Божьим подарком».