Глубокий кризис, поразивший духовную жизнь Европы, истерзанной империалистической войной, не мог не затронуть музыкального искусства. Практически все буржуазные идейные и стилевые направления, пересматривавшие и отвергавшие прежние эстетические и этические ценности, нашли отражение в музыке. Германские и австрийские экспрессионисты, и среди них Арнольд Шенберг, основоположник атональной музыки, сломавший обычные связи между звуками, французские импрессионисты и другие модернисты, отказавшиеся от классической европейской системы музыкального мышления, усиленно занимались поисками новых выразительных средств. Они или разрушали традиционные формы и на их обломках выстраивали уродливые хаотические звуковые конструкции, или пытались отыскать эстетические идеалы в «экзотике», обращаясь к музыке народов Азии, Латинской Америки, Африки и, конечно, к джазу. Привлеченные его свежестью и непосредственностью французы Клод Дебюсси, Морис Равель, Дариус Мийо, Франсис Пуленк, Жорж Орик, Артур Онеггер, немцы Пауль Хиндемит и Курт Вайль, австриец Эрнст Кшенек, русский Игорь Стравинский смело включили ритмы, интонации и оркестровые эффекты джаза в свои произведения. В концертных залах и оперных театрах звучали созданные этими композиторами «Кукольный кейк-уок» и «Негритянская рапсодия», «Фуга на джазовую тему» и «Блюзовая соната», «Рэгтайм для фортепиано» и «История солдата», «Парад» и «Опера нищих». В финале «джазовой» онеры Кшенека «Джонни наигрывает» перед слушателями возникал негр, стоявший на земном шаре, что, видимо, символизировало веру композитора и постановщика в утверждение джаза на мировой музыкальной сцене. «Негритянская музыка, открытая белыми и представленная ими в популярной форме, покорила мир» — так писал Робсон в одной из своих статей, опубликованной в 1935 году.
И все-таки музыку, которую европейцы услышали с американских граммофонных пластинок и которую исполняли заокеанские, как правило, белые гастролеры, можно было лишь условно назвать джазом. До Европы поначалу дошла его копия, причем далеко не лучшая. Освоив наиболее эффектные приемы джазового стиля, белые музыканты играли развлекательную, или, как ее называли, коммерческую, музыку, рассчитанную на чувственно-эротическое восприятие.
Настоящий джаз с его мелодическим и ритмическим богатством, способный развиться в большое искусство, пока еще не выходил далеко за пределы негритянских кварталов юродов Америки.
Поначалу Поль, как и большинство его сверстников, восторженно относился к джазу, полагая, что только эта музыка способна во всей полноте выражать присущие молодежи удаль, прямоту и жизнерадостность. Вскоре после переезда в Гарлем состоялось знакомство Робсона с Флетчером Хендерсоном, негритянским музыкантом, который уже был известен в кругах нью-йоркских меломанов. Хендерсон, оставивший ради джаза занятия химией в Атлантском университете, искал вокалиста для ансамбля «Четыре короля гармонии». Кто-то порекомендовал ему Поля, и Хендерсон, послушав несколько блюзов в его исполнении, незамедлительно предложил польщенному Робсону место в квартете.
«Четверка» успешно выступала в гарлемских ресторанах, исполняя эстрадные песенки, искусно аранжированные Хендерсоном. Популярность ансамбля росла. Его даже приглашали участвовать в музыкальных представлениях — шоу на эстраде знаменитого «Коттон-клуба».
Прекрасный музыкант и блестящий знаток негритянского фольклора Хендерсон подолгу занимался с участниками ансамбля: джазовые певцы должны хорошо владеть особой и сложной вокальной техникой. Поль довольно скоро освоил такие ее основные приемы, как глиссандо, заключающееся в скользящем переходе от звука к звуку, фальцет, достигающийся сужением краев голосовых связок, что придает пению определенную мягкость, а также вибрацию, шепот, надрыв, носовые звуки. Он с радостью сознавал, как от выступления к выступлению его голос становился сильнее, полнозвучнее, постепенно приобретал ту степень совершенства, которая превращала его в безотказный музыкальный инструмент, не знавший ни сбоев, ни фальшивых нот.
Однако чем больше времени и сил Робсон отдавал джазу, тем больше у него возникало сомнений в правильности своего выбора. Рамки джазового репертуара становились тесными для Робсона-певца. Исполняемые ансамблем песни были рассчитаны на неприхотливые вкусы завсегдатаев злачных мест и танцевальных площадок, а Поль мечтал о другой аудитории. Ему виделись большие концертные залы, заполненные доброжелательной публикой, пришедшей на его, Робсона, выступление. Он спел бы свои любимые спиричуэле, рабочие песни, блюзы без всякого аккомпанемента, чтобы ничто не мешало ему выразить их задушевность, страстность и красоту.
Хендерсон не удерживал Поля, когда тот решил покинуть ансамбль. Они расстались по-приятельски и потом изредка встречались на концертах друг друга. В 1923 году Хендерсон создал большой джазовый оркестр, который спустя несколько лет снискал широкую известность не только в США, но и на Европейском континенте.