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