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