1946年1月12日、20歳の時に逮捕され、裁判の結果、火器の不法所持・窃盗・住居侵入の罪で懲役8?10年の刑が宣告された[13]。通常、初犯者の窃盗罪では懲役2年程度の刑になることが多いため、彼が白人女性と継続的な性的関係を持っていたことが理由で、通常よりも重い刑罰になったのだとマルコム自身は考えていた[14]。収監されたチャールズタウン州刑務所では特に神と聖書を罵倒していたマルコムだったが、イライジャ・ムハンマド（英語版）の教徒の囚人からブラック・ムスリム運動（英語版）を知ることとなり、その教えを勤勉に研究した。マルコムは独学で知識を進歩させながら、イライジャと文通を始め、毎日のように手紙を書いた。異母姉のエラは、より自由のきくノーフォークのマサチューセッツ州刑務所に彼が移送されるよう支援をした。そこで彼は熱心な指導者となり、歴史上および哲学上にイライジャ・ムハンマドの教えとNOI（ネーション・オブ・イスラム）の正当性を発見した。彼は刑務所内の毎週の討論会に参加し、知識を広げ、筆跡を改善するために刑務所図書館の全辞書を筆写したりもした。刑務所内で勉強するための割り当て時間を越えて、消灯後も独房内で月明かりや通路の照明だけを頼りに読書や辞筆写していたため、収監前は2.0あった視力が0.2まで落ちることになった。そのため、後にトレードマークとなるサーモント型の近眼鏡を常用するようになる。また名を知られた後のマルコムは、出身大学を訊ねるマスコミに「刑務所内の図書館だ」と答えている。

マルコムは1952年8月7日に仮釈放（正式な釈放は1953年5月[15]）され[16]、スーツケースと眼鏡、時計を購入した。後に彼はこれらのものが「新たに始まろうとしていた人生に備えていた」と語った[17]。

マルコムが「マルコムX」と名乗ったのは1950年12月の手紙が最初である。[18]（1952年9月、彼はNOIからXという姓を授かり、これ以降「マルコムX」を名乗ったとする説もある）。アメリカ黒人の「姓」は本来の彼らの姓ではなく、奴隷所有者が勝手につけたものにすぎず、未知数を意味する「X」は失われた本来の姓を象徴するとNOIでは考え、同名の人物が同じモスクにいる場合には、入信順に「X」の前に番号をつけて○○2X、○○3X、とした。また、マルコムはXではなくシャバーズという姓を名乗る許可をNOIから得ており、1957年には広くマルコム・シャバーズと名乗っていた[19][注釈 4]。

1957年、NOIの一人が警察官に暴行を受け逮捕された。教団はこれに抗議、マルコムとFOI（Fruit of Islam、信者のうち警護等を担当する部隊）メンバーらを中心とした群衆が留置所前に集まり、仲間を病院へ送るよう要求した。この要求が受け入れられたことで、NOIとマルコムは一躍名を知られることとなった。またマルコムはサム・クックやモハメド・アリ、ビリー・ホリディらと親しく、ライオネル・ハンプトン他のジャズを見に行くなど、文化人的な面も強かった。

1962年、イライジャ・ムハマドが十代の少女に子を産ませていたことが判明したことで、NOIに失望したマルコムは彼の行為を告発する。その行為は、NOIにおける自身は立場を危うくすることとなった。1963年2月にはNOIがマルコム暗殺を試みて失敗。そしてNOIを脱退したマルコムが1964年3月にムスリム・モスク・インクを組織するに至り[21]、マルコムとNOIの緊張はさらに強くなっていた。

NOIを脱退から数週間後、彼のもとを訪れた数名のイスラム教徒の勧めに従って、マルコムはスンニ派に改宗[22][23]。翌1964年4月にはアフリカ・中東に赴き、メッカ巡礼成就の意味を込めたエル・ハジ・マリク・エル＝シャバーズへと正式に改名した。またそこで、白人でありながらも自分たち黒人を肌で判断しないアラブ人に感化され、アメリカでの「白人」とは肌の色よりも黒人を対象にしたときの態度・行動であるという新しい視点を得ることとなった。また世界中から集まったあらゆる肌のイスラム教徒が同じ儀式に参加する光景にも感銘を受けた[24]。特にジェッダで出会った元アラブ連盟初代事務局長のアブドゥル・ラフマーン・ハサン・アッザーム（英語版）博士の影響で正統派のイスラム教に目覚めることとなった。サウジアラビアのファイサル王子からは国賓として扱われたマルコム[25]は、巡礼の儀式を終えた後にファイサル王子とともに現地のイスラム教徒の歓声に応えた[26]。

さらにマルコムは、新たに立ち上げたアフリカ系アメリカ人統一機構（英語版）のリーダーとしてアフリカ統一機構の会議に出席して汎アフリカ主義の指導者と親睦を深め[27]、エジプトのガマール・アブドゥル＝ナーセルやガーナのクワメ・エンクルマなどに招待されてアフリカ諸国を歴訪した[28]。

それまでNOIに強く影響を受けた黒人至上主義者だったマルコムは、このアフリカ・中東訪問を経ることで、アメリカの黒人問題は公民権問題にとどまらない国際的な問題であるとの視点に立ち、黒人は第三世界と連帯するべきだと主張するようになった[29]。
暗殺ステージに開いた銃弾の跡「マルコム・X暗殺事件（英語版）」を参照

NOIに侵入していたFBIの潜入捜査官は、マルコムがNOIによって暗殺の対象になったと報告した。