Перед Утесовым встал вопрос о том, что ему делать в новых условиях. С частью своих товарищей он вступил в артистическую бригаду, которая разъезжала по Одесскому военному округу в составе Первого коммунистического агитпоезда и выступала в воинских частях. Утесов участвовал в этих концертах и как куплетист, и как серьезный рассказчик, а также как лирический певец, танцор, опереточный простак, читал монологи, стихи, дирижировал и играл на нескольких инструментах, В 1921 г. Утесов вместе со своим другом Нежином (будущим талантливым театральным администратором) отправился в Москву. Ехали, как говорится, наобум: в столице их никто не ждал, никакой работы и никакого жилья никто не предлагал. Впрочем, им сразу удалось устроиться на работу в Театр революционной сатиры на Большой Никитской. Здесь Утесова некоторое время использовали на вторых ролях в различных агитационных пьесах и революционных фарсах. Но развернуться ему на сцене этого театра было трудно. Осмотревшись, Утесов нашел себе работу в театре «Эрмитаж», где вскоре приобрел популярность как куплетист. В эти годы как раз начался НЭП, и в столице один за другим стали открываться частные театры. Утесова пригласили в труппу Театра музыкальной комедии, дававшей спектакли в «Славянском базаре».
За год он сыграл в различных опереттах около десятка больших и малых ролей. В 1922 г. его пригласили в Петроград в «Палас-театр», где также играла опереточная труппа. Наконец, в 1923 г. Утесов вступил в Свободный театр Юдовского, где шли по преимуществу миниатюры, перемежающиеся с эстрадными номерами. Имя его в это время было уже достаточно широко известно. Особенный успех он имел как чтец юмористических рассказов (Зощенко, Бабеля, Уткина и других авторов). Участвовал он и во многих спектаклях.
Так, в 1926 г. Утесов имел невероятный успех в роли Менделя Маранца в одноименной пьесе Фридмана. Спектакль шел каждый вечер и неизменно в продолжение пяти недель давал полный сбор. Один из рецензентов писал в это время: «Кому неизвестно, что Утесов может рассмешить и смертельно больного человека? Этот сочный актер, прекрасно чувствующий свою публику, знает, как ее расшевелить, чем ее взять…» Когда в 1928 г. он ушел из Свободного театра, тот вскоре закрылся, так как весь репертуар держался на одном Утесове. В 1925 г. он между прочим снялся в двух фильмах Светлова — «Карьера Спирьки Шпандыря» и «Чужие» и в обоих играл главную роль.
В 1928 г. Утесов пришел работать в Ленинградский театр сатиры. Однако профессия актера привлекала его все меньше и меньше. В 1927 г. он побывал за границей, в Берлине и Париже, и здесь впервые услышал первоклассную джазовую музыку в исполнении оркестров Джека Хилтона и Тэда Льюиса. (До этого в Советском Союзе ему приходилось слышать лишь подделки под джаз.) Возвратившись в Ленинград, Утесов тотчас начал создавать свою джаз-группу.
Дело это было совершенно новое и потому очень трудное. Заниматься им приходилось в свободное от основной работы время, денег музыкантам никто не платил. Однако благодаря широким знакомствам в музыкальных кругах Утесову удалось собрать сильный оркестр из первоклассных музыкантов. Он увлек своим замыслом контрабасиста Игнатьева, который хорошо оркестровал, что было очень важно, так как в то время джазовых оркестровщиков почти не было. Так же очень помог Утесову первоклассный трубач Скоморовский, взявший на себя обязанности музыкального руководителя оркестра. С их помощью было создано и разучено несколько джазовых композиций. Но Утесову было мало того, что оркестр располагал отличными исполнителями, он хотел, чтобы каждый из музыкантов был на сцене актером. Ему хотелось, чтобы они, словно подхваченные властным ритмом мелодии, подтанцовывали на месте или, будто поддавшись печальной мелодии, оттеняли ее плавным покачиванием. От каждого он добивался раскованности, полной свободы самовыражения и импровизаций. Сам он выступал в качестве конферансье, вокалиста и дирижера, исполнив таким образом свою детскую мечту. Первую программу, названную «Теа-джаз», репетировали полгода.
Первое выступление состоялось в Международный женский день 8 марта 1929 г. во время концерта в Малом оперном театре. Утесов исполнял роль конферансье, танцевал, играл на скрипке и вел комические беседы с музыкантами. Успех превзошел все ожидания — это был подлинный триумф. Через несколько дней оркестр дал еще один концерт в саду имени Дзержинского, затем отправился на гастроли по курортам Северного Кавказа, а по возвращении был приглашен на открытие сезона в Московский Мюзик-холл. Интерес к «Теа-джазу» был огромный. Великолепное мастерство музыкантов, прекрасные голоса солистов, зажигательная музыка, артистический талант самого Утесова — все создавало оркестру успех. В дальнейшем состав его постоянно менялся, старые музыканты уходили, на их место являлись новые. Постоянный костяк сложился только через десять лет. К концу 30-х гг. в оркестре Утесова было пять саксофонистов, два тромбониста, три трубача, два скрипача, пианист, контрабасист и исполнитель на ударных инструментах. Все они были истинными фанатиками джаза, выдающимися мастерами и артистами — раскованно держались на сцене, стремились играть роли, шутить, подпевать солисту и даже танцевать. Между тем в репертуаре оркестра было множество сложнейших произведений, требовавших от исполнителей подлинной виртуозности.
Утверждение джаза на советской эстраде протекало не без борьбы. В то время как публика приняла оркестр Утесова «на ура», критика далеко не была к нему так благосклонна. Особенно доставалось ему от пролеткультовцев, которые объявили джаз «типичным порождением буржуазного мира» и начали против него беспощадную борьбу. Вообще в те годы относились очень подозрительно к легкой лирической музыке. Один из авторитетных музыковедов писал в начале 30-х гг.: «Что мы называем легкожанровой музыкой? Это музыка бара, кафешантана, варьете, «цыганщина», джазовая фокстротчина и т. д., все то, что составляет некий музыкальный самогон, что является художественной формой использования музыкального звучания не для поднятия масс, а для того, чтобы душить их инициативу, затемнять их сознание».
Утесов, между тем, отдавал предпочтение именно этой «легкожанровой» музыке. (Например, гвоздем его первых концертов стала блатная песенка «С одесского кичмана», которую он исполнял в шутливо-иронической манере.) Нападки на него и его оркестр происходили постоянно. Так, в 1930 г. журнал «За пролетарскую музыку» писал об одном из его концертов: «Что же представляло собой само выступление Утесова? Кривляние, шутовство, рассчитанное на то, чтобы «благодушно» повеселить «господина» публику… На это безобразие должна обратить внимание вся советская общественность. Необходимо прекратить эту халтуру. Нужно изгнать с советской эстрады таких гнусных рвачей от музыки, как Л. Утесов и K°». Отвечая на подобные опусы, Утесов доказывал, что его джаз по своей природе бодр и жизнерадостен и что он порожден оптимизмом «эпохи индустриализации». Оппонентами его были не только теоретики пролеткульта, но и более могущественные деятели советской культуры. Против джаза активно выступали нарком просвещения Луначарский и писатель Максим Горький. Утесову пришлось много поработать, чтобы лишить джазовую музыку ее «буржуазного» привкуса и сделать ее по возможности «советской».
В 1932 г. оркестр выступил с новой (третьей по счету) программой «Музыкальный магазин», которая считается одной из лучших в его истории. Это был не просто концерт, это было целое театральное действо, потрясающе смешное, остроумное и интересное. С огромным успехом программа была показана во многих городах, всюду вызывая восторженные отклики. Тогда возникла идея перенести эту программу на экран. Утесов согласился, но предложил написать специальный сценарий. Так родилась идея фильма «Веселые ребята» — первой советской музыкальной комедии. Ставил ее Александров, музыку написал Дунаевский, а тексты песен — молодой и тогда еще малоизвестный поэт Лебедев-Кумач. На роль главной героини была приглашена Любовь Орлова. Фильм вышел на экраны в конце 1934 г. и, как уже говорилось, имел невероятный успех у зрителя. После него Утесов приобрел не только всенародную популярность как певец (в предвоенном репертуаре особой любовью пользовались песни: «Нам песня строить и жить помогает», «Песня старого извозчика», «Все хорошо, прекрасная маркиза», «Раскинулось море широко», «Каховка», «Коса», «Тачанка»), но и стал настоящей кинозвездой.
