Между тем страсть своего отпрыска к театру родители Бернеса категорически не одобряли. Их мнение было твёрдым и однозначным: он должен продолжать учёбу в торгово-промышленном училище и забыть о театре. Однако переубедить упрямого Бернеса не смогли даже родители. В 17 лет он попросту сбегает от них: садится в поезд и уезжает в Москву. В столице он несколько дней живёт на Курском вокзале, а днём обивает пороги столичных театров, соглашаясь на любую работу. И наконец он добивается своего: его берут в массовку Малого театра. Одновременно он успевает записаться и в массовку Большого театра, благо они находятся рядом. Так проходит несколько месяцев.

В феврале 1930 года Бернес подаёт заявление в Московский драматический театр (бывший Корша) и получает положительный ответ. Он становится актёром вспомогательного состава. Его рвение в работе столь велико и заметно, что уже через 11 месяцев — в январе 1931 года — его зачисляют актёром в основной состав. Однако роли в спектаклях ему достаются небольшие. Таких ролей за три года работы в драмтеатре он сыграет пять.

Своего угла в Москве Бернес долгое время не имел, поэтому первые несколько месяцев ему пришлось жить в крохотной гримёрной. В доме напротив театра в Петровском переулке надстроили этаж (пятый) и одну из его комнат отдали молодому актёру. В начале 1933 года он перешёл работать в Театр революции.

В середине 30-х годов он женился на молодой девушке, которую звали Полина (друзья Марка называли её Паолой или просто Пашей). Именно она стала прививать Бернесу интерес к литературе, заразила его чтением.

В 1935 году началась его театральная слава. Режиссёр Евгений Червяков задумал снимать художественный фильм «Заключённые» и на главную роль пригласил Михаила Астангова. А тот, в свою очередь, порекомендовал взять на одну из эпизодических ролей 24-летнего актёра Марка Бернеса. И хотя его появление в этом фильме прошло незамеченным, дружба с Астанговым осталась надолго. Тот познакомил друга с драматургом Николаем Погодиным, который, в свою очередь, «сосватал» молодого актёра режиссёру Сергею Юткевичу. Тот в 1936 году приступил к съёмкам фильма «Шахтёры» и искал артиста на роль шпиона Красовского. И Бернес подошёл на эту роль.

Ровно через год после съёмок Юткевич приглашает Бернеса в свой новый фильм — «Человек с ружьём», где ему вновь достаётся эпизод, однако на этот раз его персонаж герой положительный — молодой красноармеец. Роль по сценарию выглядела несложной, однако Бернес решил подойти к её исполнению творчески. В течение нескольких дней перед началом съёмок он не вылезал из Музея революции, пытаясь найти среди фотоэкспонатов музея образ нужного ему молодого красноармейца. И в конце концов нашёл — молодого вихрастого паренька, перепоясанного крест-накрест пулемётными лентами. Однако чего-то его экранному герою всё-таки не хватало. Но чего? Бернес этого и сам пока толком не знал. Но стал копаться в актёрском реквизите и внезапно наткнулся на старенькую гармонь. Так была найдена ещё одна важная деталь. А затем на свет родилась и песня: второй режиссёр фильма Павел Арманд сочинил нехитрую песенку «Тучи над городом встали», которую герой Бернеса — Костя Жигулёв — и запел с экрана. Когда фильм снимался, никто из участников съёмок и предположить не мог, что эта песня в исполнении Бернеса вскоре станет народным шлягером. Так после фильма «Человек с ружьём» 26-летний М. Бернес стал знаменит.

В 1938 году успех Бернеса в мире кино закрепляет режиссёр Эдуард Пенцлин: он не только приглашает актёра на главную роль в свой фильм «Истребители», но и делает его героя — лётчика Сергея Кожухарова — поющим. Песня «В далёкий край товарищ улетает» (композитор Н. Богословский) туг же становится шлягером. Фильм занимает 1-е место в прокате 1940 года, собрав на своих сеансах 27,1 млн. зрителей.