С этого момента у Мессинга началась совсем другая жизнь. Поначалу ему пришлось туго — русского языка он почти не знал, а о его карьере в стране Советов никто не слышал, да и не жаловали здесь предсказателей и ясновидящих. Мессингу все же удалось попасть в состав концертной бригады, обслуживавшей приграничный Брестский район. Его «психологические опыты» понравились, и в мае 1940 года Мессинг уже гастролировал сначала в Минске, а затем и по всей Белоруссии. Новая жизнь казалась артисту странной, но главное — он продолжал жить. Его близким повезло меньше; известий об отце и братьях Мессинг не получал, но точно знал, что никого из них в живых больше нет. Позднее он узнает, что вся его семья погибла в газовых камерах концлагеря Майданек.
Одна из самых загадочных страниц биографии Мессинга связана с И. Сталиным. Однажды в Гомеле к артисту на сцене подошли двое в форме НКВД и, извинившись перед публикой за прерванное представление, увезли его в Москву, к Сталину. О том, как произошла эта встреча, Мессинг рассказал в книге «О самом себе»: «Входит какой-то человек с усами. Здоровается. Я его узнал, сразу отвечаю: „Здравствуйте. А я вас на руках носил“. — „Как это на руках?“ — удивился Сталин. „Первого мая, на демонстрации“…»
О чем они разговаривали позже, во время других встреч, Мессинг не упомянул вовсе. Известно, что «отец народов» несколько раз устраивал ему проверки. Предложил, например, получить в Госбанке по чистой бумаге большую сумму денег — 100 000 рублей. Вольф Григорьевич вспоминал: «Я подошел к кассиру, сунул ему вырванный из школьной тетради листок. Раскрыл чемодан, поставил у окошка на барьер. Пожилой кассир посмотрел на бумажку. Раскрыл кассу, отсчитал сто тысяч… Закрыв чемодан, я отошел к середине зала. Подошли свидетели, которые должны были подписать акт о проведенном опыте. С тем же чемоданчиком я вернулся к кассиру. Он взглянул на чистый тетрадный листок, затем неожиданно опустился на спинку стула и захрипел… Инфаркт… К счастью, он потом выздоровел». Второе задание оказалось сложнее: Мессинг должен был без документов и пропуска войти в кабинет Берии, а затем выбраться из здания Наркомата внутренних дел на улицу. Ему удалось и это. Доказав свои способности, Мессинг получил право продолжать выступления, однако, не соблюдая политической осторожности, часто попадал в опасные ситуации. Так, после подписания пакта Молотова-Риббентропа все советские люди должны были поверить в нерушимую дружбу двух социалистических государств: нацистской Германии и большевистской России, а вся советская пресса славила мудрость Сталина, предотвратившего войну. Вот в этой то вымученно-оптимистической атмосфере Мессинг, выступая в клубе НКВД, получил записку с вопросом «Что вы думаете о советско-германском пакте?» Последовавший ответ: «Я вижу танки с красными звездами на улицах Берлина» — произвел эффект разорвавшейся бомбы. «Как, усомниться в мудрости Сталина?» За меньшее в те годы расстреливали без суда и следствия. Но «вождь народа» решил проверить предсказание — приказал подождать. Выступления Мессинга были прекращены, афиши с его именем исчезли. А 22 июня 1941 г. пророчество Мессинга, хотя и частично, но исполнилось: пакт был нарушен, Германия напала на СССР. Прорицатель был «прощен», вернулся на сцену, часто выезжал с концертными бригадами на фронт. На заработанные деньги он построил и подарил летчикам два боевых самолета: первый — в 1942 году, второй — в 1944-м. Согласно легенде, впоследствии Сталин неоднократно приглашал к себе Мессинга, чтобы тот консультировал его по поводу событий на фронтах Второй мировой войны. В Новосибирске, отвечая на вопрос, когда закончится война, телепат сказал: «Восьмого мая», — но года не назвал. Сталин пристально следил за пророчествами Мессинга и, когда акт капитуляции Германии был подписан, послал ему телеграмму, отметив точность даты.
По Москве ходили слухи, что Мессинг отсоветовал любимому сыну Сталина Василию лететь в Свердловск вместе с хоккейной командой ВВС. Отец якобы велел ему ехать поездом — и Василий добрался до Свердловска целым и невредимым. Самолет же, в котором летели хоккеисты, разбился, все пассажиры, находившиеся на его борту, погибли. На самом деле так было или это очередная легенда, которых в жизни знаменитого иллюзиониста было немало, неизвестно.