Практически сразу после переезда в Москву утёсовский оркестр был передан в ведение театрального отдела Центрального дома Красной армии (ЦДКА). Это был не в переносном, а в прямом смысле слова подарок судьбы. Прежде всего потому, что руководители отдела, вполне справедливо считая себя некомпетентными в вопросах искусства, не вмешивались в работу оркестра. В коллективе оставалось много ленинградцев, которые с удобством разместились в гостинице ЦДКА. Оркестр получил две великолепные концертные площадки — Краснознаменный зал (зимой) и Летний театр. В день прилета Чкалова в Москву, 13 августа, весь оркестр был приглашен на прием в Кремль. Волновались все, но больше всех Утёсов. Он не без основания полагал, что к нему не очень благоволят в «верхах». Вплоть до этого времени Утёсов не был отмечен ни одной правительственной наградой — и это при его популярности!
В Кремль отправились в полной амуниции — то есть так, чтобы, выйдя из автобуса, можно было сразу приступить к выступлению. Прием предполагался в Георгиевском зале. Когда открылись двери в этот знаменитый зал — до этого никто из музыкантов, включая Утёсова, не бывал здесь, — открывшийся вид так взволновал оркестрантов, что никто не мог проронить даже слова. Разумеется, все взгляды были направлены в ту сторону, где за столом сидели члены правительства во главе со Сталиным, а рядом с ними — чкаловский экипаж. Буквально не дыша, оркестранты прошли к эстраде, сооруженной вблизи главного стола. Сидящие за столом вели себя раскованно, ели, пили, веселились.
После официальной части — заметим, что никто не навязывал оркестру репертуар, — к Утёсову подошел Климент Ефремович Ворошилов и передал просьбу самого Сталина исполнить «С одесского кичмана», «Бублички» и другие «блатные» песни. После каждой песни раздавались не просто аплодисменты, а настоящая овация. А потом Ворошилов пригласил Утёсова к главному столу. Большинство вождей здоровались с Леонидом Осиповичем за руку и охотно выпивали с ним. Сталин был явно в хорошем настроении, но вскоре незаметно ушел. Из зала убрали стулья, и началось обыкновенное народное веселье — все танцевали, пели. К Утёсову подошли сначала его знакомый Тухачевский (напомним, он подарил артисту саморучно сделанную скрипку), а потом Ворошилов. Он торжественно произнес при всех, но явно для оркестра, указывая на Тухачевского: «Это первый военный в нашем государстве, хотя и с белой косточкой». И, глядя в упор на маршала, спросил: «Миша, тебе можно верить?» Не прошло и года, как Тухачевского объявили врагом народа и расстреляли…
После общения с вождями оркестрантов отвели в специальную комнату, где было подготовлено особое «кремлевское» угощение. Едва ли кто-то из них не только ел, но и видел такие яства. Утёсов не делился, о чем шла речь за «хозяйским» столом, но сказал оркестрантам: «Мы еще не осознали, какое счастье нам выпало». И уже по пути домой, в автобусе, когда он выехал за ворота Кремля, сказал: «Мог ли я когда-нибудь подумать, что я, одесский еврей с Молдаванки, буду находиться в Грановитой палате, петь для Сталина и пить с вождями водку?»
Вскоре в «Известиях» была опубликована заметка Утёсова «Встреча в Кремле»: «С затаенным дыханием я следил за полетом наших героев по сталинскому маршруту. У меня тогда родилась надежда, что на мою долю выпадает великая радость показать свое искусство тем, кто так высоко поднял знамя нашей родной советской авиации. Но даже в самых смелых своих мечтах я никогда не лелеял мысль выступить в присутствии вождей Великой пролетарской революции. Я думаю, что в моем лексиконе не найдется достаточно ярких слов, чтобы связно передать свои впечатления от выступления в Кремле 13 августа. Я никогда в жизни так не волновался, как в этот вечер. Но с первого же момента нашего появления на эстраде, когда я увидел столь знакомое мне по портретам лицо великого вождя народов т. Сталина, я почувствовал такое воодушевление, какое никогда в жизни не испытывал. Несколько ободряющих слов сказал мне великий полководец Маршал Советского Союза К. Е. Ворошилов. Только человек с большим сердцем мог так почувствовать переживания актера и ободрить его в столь важную минуту его жизни. Спасибо, спасибо ему за это!
А наши герои? Сколько в них скромности. Они не пытаются даже дать почувствовать, что ими совершен величайший подвиг. Смотришь в глаза Героям Советского Союза и видишь простых, чудесно простых людей — Чкалова, Байдукова, Белякова. Вот они герои, люди нашей страны. Так разве же не счастье получить возможность своим искусством доставить им радость. Я бесконечно счастлив, что мне и моему коллективу выпала огромная честь выступать в Кремле в присутствии великого Сталина и Героев Советского Союза».