В «Варьете-Амюзант» Леметр задержался недолго, он перешел в театр «Фюнамбюль», где сыграл более десяти самых разноплановых ролей. Вынужденный поставить имя на афишу и боясь домашнего скандала, Проспер Леметр впервые выступил здесь под фамилией Фредерик, которая на всю жизнь стала его сценическим псевдонимом, соединившись позднее с настоящей фамилией — Леметр.
Один из посетителей театра рекомендовал его актеру «Комеди Франсез», профессору консерватории Мишло. Так Фредерик-Леметр попал в класс трагедии.
Занимаясь в консерватории, он оставался актером пантомимы. В 1818 году Фредерик-Леметр перешел из «Фюнамбюля» в «Олимпийский цирк». Работа в театре пантомимы заложила фундамент его будущих творческих побед.
В июне 1820 года он поступил в труппу театра «Одеон», где провел три сезона, после чего оказался в «Амбигю-Комик».
2 июля 1823 года Фредерик-Леметр сыграл беглого каторжника Робера Макэра в мелодраме «Постоялый двор Андре» Антье, Сент-Амана и Полианта. Фредерик перевел мелодраму в комедийный план. Причем комедийное звучание ролей раскрылось только на премьере, что стало сюрпризом даже для авторов пьесы. Как замечает российский театровед Г.Б. Асеева, «родился яркий, стремительный, озорной спектакль, в котором господствовала импровизация, шутка, трюк. В центре действия был обаятельный, отчаянно храбрый и бесконечно наглый, циничный и остроумный беглый каторжник Робер Макэр, смело вступающий в единоборство с полицией и весело перебрасывающий в ложи трупы убитых жандармов». Спектакль имел оглушительный успех. Правда, после восемьдесят пятого представления цензоры запретили «Постоялый двор».
За четыре сезона в театре «Амбигю-Комик» Фредерик-Леметр сыграл 25 ролей и выступил на сцене 980 раз! При этом, почти всегда играя центральные роли, он успел еще на стороне, в маленьких театриках появиться в трех прославленных ролях Тальма (Отелло — в том числе), а также написать две пьесы.
Скоро пришли роли, которые требовали более сложных внутренних ходов. Среди них этапными для Фредерика стали Кардильяк («Кардильяк, или Квартал Арсенала», 1824) и Калиостро («Калиостро», 1825) в пьесах Антони и Леопольда. Шумный успех этих спектаклей вывел Фредерика в ряды лучших актеров Парижа. С этого времени за ним закрепляется прозвище «Тальма бульваров». Его отмечает пресса. «Одаренный весьма замечательным театральным инстинктом, — сообщала газета „Пандора“, — Фредерик ни в коей мере не обладает напыщенностью прежних актеров мелодрамы… Он проникается чувствами персонажа, у него есть пыл, естественность». Это мнение еще больше укрепилось, когда он сыграл роль извозчика Дюпре, по прозвищу Руль-Пари («Перекати-Париж») в мелодраме Бенжамена и Рюбена «Извозчики» (1825).
В 1826 году Леметр женился на актрисе Софи Аллинье, три года игравшей с ним в «Амбигю». Правда, свадебный бал пришлось отменить: перед его началом по Парижу распространилась скорбная весть — скончался кумир Леметра, великий трагик Тальма. Тень этой грустной увертюры как будто омрачила судьбу молодой пары — их семейная жизнь сложилась неудачно…
Фредерик-Леметр понимает, что перерос рамки театра «Амбигю», и в 1827 году переходит в театр «Порт Сен-Мартен», где дебютирует в мелодраме «Тридцать лет, или Жизнь игрока» Дюканжа и Дино. Ее герой Жорж Жермани — игрок, одержимый безумной страстью, приводящей его к гибели. Фредерик и его партнерша Дорваль достигли той гипнотической силы воздействия, которая поражает в романтических актерах. В кульминационном третьем действии крики ужаса неслись со всех концов зала, а на премьере один из зрителей потерял сознание и его пришлось вынести.
Спектакль произвел фурор. Сценическая встреча Фредерика и Дорваль стала откровением для самих актеров — до сих пор они не имели партнеров равной силы и не знали подобной полноты творческого взаимопонимания. Критик Жюль Жанен писал, что Фредерик и Дорваль «произносили напыщенные и тяжеловесные фразы совершенно просто и естественно и превращали драмы, в которых актеры рычали, в простой разговор… Эти два артиста совершили полную революцию в драматическом искусстве. И тотчас же зрители, привыкшие к завываниям мелодрамы, ко всему этому шуму голосов и слов, стали с удивлением переглядываться, растроганные и очарованные…» Во всех отзывах звучала одна и та же мысль: «Это ужасающе правдиво».
25 марта 1828 года в «Порт Сен-Мартен» состоялась премьера драмы Дюканжа «Ламермурская невеста». Эта пьеса уже вплотную приближалась к романтической драме. Трагическая история Люси Астон (Дорваль) и Эдгара Равенсвуда (Фредерик), проносящих свое большое и сильное чувство через море лжи и насилия, прозвучала как гимн высокой романтической любви, обреченной на гибель, но воспевающей идеал человечности. И на этот раз Фредерик и Дорваль поразили зрителей поэтичностью, страстью, красотой.
После триумфальных гастролей по городам Франции Фредерик впервые был приглашен в Лондон. Вскоре он сообщал из столицы Англии: «Успех превзошел все мои ожидания!»