В середине декабря Поль снова приезжает в Москву, предполагая совершить большую концертную поездку по городам Советского Союза. Однако его намерениям было не суждено осуществиться. Участившиеся головные боли, доводившие Поля до полуобморочного состояния, вынудили обратиться к врачам. После всестороннего обследования Робсона в одной из московских клиник врачи определили у него атеросклероз с нарушением кровообращения в сосудах головного мозга и, запретив Полю заниматься концертной деятельностью, назначили длительный курс лечения.
Через несколько месяцев в состоянии здоровья Робсона наступили заметные улучшения: могучий организм певца, казалось, преодолел тяжелый недуг. Даже видавшие виды врачи были поражены столь быстрым отступлением болезни. В конце концов они согласились с настоятельными просьбами Поля и разрешили ему участвовать весной 1959 года в спектакле «Отелло» Шекспировского мемориального театра.
Робсон был счастлив в третий раз обратиться к любимой роли. Спектакль ставил тридцатилетний режиссер Тони Ричардсон, известный своими театральными и кинематографическими работами, в которых критически осмысливался буржуазный образ жизни.
Времени до премьеры, которой должен был открыться очередной сезон в Шекспировском театре, оставалось мало, поэтому в день проводилось по две репетиции, вторая часто заканчивалась далеко за полночь. Поль радовался, видя стремление молодого режиссера создать спектакль современный, свободный от архаики, подражательности и штампов, не отступая при этом от лучших реалистических традиций Шекспировского театра. Из актеров он сразу выделил одаренного двадцатилетнего Альберта Финни, репетировавшего роль Кассио. (Поль не ошибался, предрекая Финни большое будущее. В 1963 году актер получил всемирную известность, блистательно сыграв главную роль в кинофильме «Том Джонс», поставленном Тони Ричардсоном по роману классика английской литературы Г. Филдинга «История Тома Джонса, найденыша».)
Премьера «Отелло» состоялась 7 января 1958 года, незадолго до дня рождения Робсона. Пятнадцать раз опускался и поднимался занавес по окончании спектакля: зрители горячо благодарили его создателей. Театральная критика, в целом положительно оценивая постановку Ричардсона, особенно отмечала превосходную игру Робсона. «Это потрясающий Отелло, — восторгался рецензент газеты «Бирмингем мейл». — Поначалу мне казалось, что в спектакле отсутствует дух Шекспира, но вот появился Робсон, и мы увидели Отелло нашего времени. Сила Робсона-актера рассеяла сомнения». Видный английский театральный критик Чарлз Грейвз, с похвалой отозвавшись об игре Робсона, писал, что «годы придали его Отелло зрелости, которой он, возможно, не имел раньше». И все-таки самым приятным свидетельством творческого успеха было для Робсона признание юных зрителей-школьников Стратфорда-он-Эйвон, подаривших ему статуэтку Отелло.
В 1960–1962 годах Робсон неоднократно гостил в СССР по приглашению Советского комитета защиты мира и Комитета по международным Ленинским премиям «За укрепление мира между народами». И хотя врачи, беспокоясь о его самочувствии, рекомендовали Полю воздерживаться от частых выступлений, он использовал любую возможность для общения с советскими людьми, приезжал на автозавод имени И. А. Лихачева, встречался с московскими железнодорожниками, с рабочими и работницами комбината «Трехгорная мануфактура». Он пел им свои лучшие песни, говорил о том, что «в нынешнем быстро меняющемся мире само существование Советского Союза имеет огромное значение для борьбы народов за свободу, за полное равноправие и человеческое достоинство».
Двадцать третьего декабря 1963 года Робсон возвратился в Нью-Йорк. В течение пятилетнего пребывания за рубежом он пристально следил за событиями, происходившими на родине. Знал о небывалом подъеме массового движения против сегрегации и расизма, которое возглавлял темнокожий священник из Атланты Мартин Лютер Кинг, избравший гандистскую концепцию ненасилия основным методом борьбы негров за свои права. Знал и о появлении в США в конце пятидесятых — начале шестидесятых годов различных негритянских экстремистских групп, лидеры которых, наметив целью создание в Северной Америке отдельного негритянского государства, прямо призывали к партизанской войне против белого населения США.