В 1956 году Мкртчян уехал в Ереван и поступил в труппу театра имени Сундукяна. Когда актер этого театра Хорен Абрамян спросил новичка, что он заканчивал, Мкртчян ответил: «Музыкальный техникум по классу виолончели». Ему хотелось сразу произвести впечатление на своих новых партнеров. Однако обман тут же вскрылся. Абрамян обратился к оркестрантам с просьбой дать новичку виолончель, на что Мкртчян замахал руками: «Зачем я буду играть, у меня есть бумага, что я учился». С тех пор за Мкртчяном в новом театре закрепилось прозвище Виолончелист.
Начиная свою карьеру на новом месте с незначительных ролей, Мкртчян уже к началу 60-х сумел выбиться в лидеры. И зритель ходил в театр уже конкретно на Мкртчяна. Как итог: на талантливого актера обратили внимание кинематографисты. До этого он снялся в кино только один раз – в картине «О чем шумит река» 1959 года выпуска он сыграл крохотный эпизод. Но в 1960 году режиссеры Г. Малян и Г. Маркарян пригласили Мкртчяна на роль более масштабную – в фильме «Парни музкоманды» он сыграл веселого музыканта Арсена. Однако, несмотря на успех фильма в Армении, следующих ролей Мкртчяну пришлось ждать целое пятилетие.
Слава пришла к Мкртчяну во второй половине 60-х – правда, к ней актеру пришлось буквально продираться. «Крестным отцом» армянского актера стал режиссер-грузин Георгий Данелия, который в 1965 году предложил ему пусть небольшую, но запоминающуюся роль профессора Берга в своей комедии «Тридцать три». Однако дебют, что называется, не прогремел, но не по вине актера – фильм посчитали идеологически вредным и быстро сняли с проката.
Еще печальнее сложилась судьба другой комедии с участием Мкртчяна – «Формулы радуги» Георгия Юнгвальд-Хилькевича, где актер сыграл милиционера. Эту картину и вовсе не выпустили в прокат и на двадцать лет упрятали в запасники Госфильмофонда. Так что две первые большие роли в кино Фрунзе Мкртчяна оказались под запретом.
И все же слава нашла своего героя. В 1966 году великий комедиограф Леонид Гайдай пригласил Мкртчяна в свой кинохит «Кавказская пленница» на роль Джабраила – родного дяди той самой «комсомолки, спортсменки и просто красавицы», из-за которой в фильме и разгорелся весь сыр-бор. И после того как фильм вышел в широкий прокат (в начале апреля 1967 года) и стал его лидером, имя Мкртчяна наконец прогремело на всю страну. Кстати, роль киношной жены дяди «кавказской пленницы» сыграла настоящая жена Мкртчяна – актриса Донара Мкртчян.
В первый раз Мкртчян женился, когда еще только начинал свою карьеру в театре. Его избранницей стала девушка по имени Кнара, которая не имела никакого отношения к искусству. Они познакомились на улице и достаточно быстро поженились, хотя у них не было даже постоянной крыши над головой. Именно бытовые проблемы и погубили этот брак: вскоре после свадьбы молодые расстались.
Во второй раз Мкртчян женился в середине 50-х. На этот раз он выбрал себе в жены свою коллегу – молодую актрису по имени Донара. Девушка приехала в Ленинакан поступать в театрально-художественный институт и попросила Мкртчяна помочь ей в этом. Тот помог, а потом сделал девушке предложение руки и сердца. Она его приняла.
Первое время этот брак приносил Мкртчяну одни радости. Молодые искренне любили друг друга, родили на свет двух детей: дочь Нунэ и сына Вазгена. Актер гордился своей красавицей женой и всячески старался ей помочь, даже в карьере. Он добился ее приема в Ереванский театр имени Сундукяна, уговорил Гайдая снять ее в эпизодической роли своей жены в «Кавказской пленнице». Но это был единственный случай, когда Мкртчян попросил кого-то из режиссеров пристроить его жену в свою картину. И в следующем своем «звездном» фильме, «Айболите-66», актер снимался уже без своей жены.
Режиссер фильма Ролан Быков нашел Мкртчяна случайно. Весной 66-го Быков позвонил своему приятелю Фрунзе Довлатяну, с которым он подружился после съемок фильма «Здравствуй, это я!», и попросил его подыскать и прислать фотографию актера на роль разбойника из шайки Бармалея. Довлатян ответил: приезжай сам, познакомишься на месте. Быков так и сделал. И вот, когда они с Довлатяном сидели и пили коньяк, в их кабинет зашел Мкртчян и буквально с первого же взгляда загипнотизировал Быкова. Тот уже забыл о всех присутствующих и был увлечен только Мкртчяном: слушал его рассказы, заразительно хохотал, когда тот показывал какие-то сценки. В конце того вечера Быков от души поблагодарил Довлатяна: «Ты мне подарил солнце».
К началу 70-х Мкртчян уже считался одним из самых популярных актеров советского кино. И хотя большинство его поклонников ценили в нем прежде всего талант комика, однако сам Мкртчян считал себя актером разных амплуа. И во второй половине 60-х он снимался в разных фильмах: и в комедиях («Белый рояль», «Не горюй!», «Адам и Хева»), и в разного рода драмах («Из времен голода», «Треугольник», «Взрыв после полуночи»). Однако в самом конце 60-х карьера Мкртчяна едва не завершилась.