Thập niên 1920, ông chuyển đến Leningrad và lập nên một trong những ban nhạc jazz đầu tiên của Liên Xô. Tại Leningrad, ông bắt đầu hợp tác với nhà soạn nhạc nổi tiếng Isaak Dunayevsky, tạo nên bước đột phá cho sự nghiệp của cả hai. Vào thời điểm đó, Utyosov đã gây dựng được một ban nhạc gồm những nhạc sĩ giỏi nhất ở Leningrad, đồng thời tạo ra phong cách của riêng mình, đó là một chương trình nhạc jazz kèm tấu hài độc thoại, pha trộn nhiều phong cách, từ các bài dân ca Nga đến các thể loại mang nét văn hóa đa quốc gia. Năm 1928, Utyosov lưu diễn châu Âu và tham dự buổi biểu diễn của các ban nhạc jazz Mỹ ở Paris, Pháp, tạo nên ảnh hưởng đến phong cách của bản thân ông. Trong thập niên 1930, Utyosov và ban nhạc "Thea-Jazz" (ghép từ "Theatrical Jazz") của ông thường xuyên diễn tại Hội trường Cẩm thạch thuộc Cung văn hóa Kirov ở Leningrad. Trong các buổi biểu diễn của mình, Utyosov mang đến cho khán thính giả nhiều phong cách âm nhạc, bao gồm các thể loại như jazz Mỹ, tango Argentina, chanson Pháp, nhảy upbeat và dân ca Nga.