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