1944년 폴란드, 비오는 진흙탕길을 유태인들이 끌려간다. 그중에 한소년이 가족들과 뿔뿔히 흩어지게 되자, 울구불구 난리를 치며 엄마를 부른다. 그리고는 닫힌 철조망문을 초능력으로 넘어트리는게 아닌가! 몽둥이를 맞고서야 쓰러지는 소년. 이장면은 엑스맨 1편의 첫장면과 동일하다. 같은해인 1944년 뉴욕, 한 소년이 야구배트를 흔들며 내려오다가 부엌에서 엄마를 만나다. 하지만 한눈에 엄마가 아니라는 것을 알아차린다. 그녀는 어린 미스틱이였다. 그 소년은 바로 찰스 자비에였고... 같은 시기 독일에서는 세바스찬 쇼우(케빈 베이컨)가 어린 에릭 랜셔을 붙잡고 그의 초능력을 끌어 내려고 애를 쓴다. 그의 엄마까지 죽이면서... 이에 분노하는 에릭은 초능력이 쏟아진다.

찰스 자비에(제임스 맥어보이)와 에릭 랜셔(마이클 패스벤더)가 각각 ‘프로페서 X’와 ‘매그니토’라는 이름을 얻기 전인 1962년 냉전 시대. 이상적인 환경에서 자라 유전자학을 공부하는 찰스는 자신에게 특별한 텔레파시 능력이 있음을 깨닫고 ‘돌연변이’의 존재에 대해 자각하기 시작한다. 그러던 중, 주변의 금속을 마음대로 제어할 수 있는 강력한 능력을 가진 에릭을 만나 절친한 친구가 된다. 반면, 인류를 지배하려는 집단 ‘헬파이어 클럽’의 수장 세바스찬 쇼우는 미국과 러시아 간의 핵전쟁을 도발해 3차 세계대전을 일으키려 하고, 이들을 막기 위해 CIA에서는 찰스와 에릭에게 도움을 요청하게 된다.

의기투합한 두 사람은 CIA 모이라(로즈번)요원과 손잡고 돌연변이 부서를 설립하고 세계 각지를 돌며 때론 ‘다르다’는 이유로, 혹은 안전하지 못하다고 차별 받는 돌연변이들을 규합해 ‘헬파이어 클럽’에 대항할 수 있는 ‘엑스맨’ 팀을 만들기 시작한다. 그 와중에 돌연변이와 인간이 평화롭게 공존할 수 있다고 믿는 찰스와 달리, 에릭은 전쟁 중에 일어난 비극적인 과거사로 인간에 대한 불신의 골이 깊어 인간의 선의에 회의를 느낀다. 이러한 시각 차이로 인해 두 사람의 우정은 흔들리는데…

우선은 미국측 요청으로 에릭과 찰스는 쇼우의 보트로 첫사움을 시작하는데 서서로 상대편의 텔레파시를 읽고 있다는것에 쇼우와 에릭은 놀란다. 이때 쇼우는 특수제작된 헬맷을 쓰고 자신의 생각을 읽히지 않돌록 한다. 그리고 유유히 사라진다. 한편 돌연변이 연구소에는 맥코이, 다윈, 엔젤, 왕발, 미스틱등 젊고 새로운 친구들이 훈련을 하고 있다. 쇼우는 계획대로 러시아의 장군을 포섭하여 미국의 쿠바를 공격하게 만들어 미국이 이에 대응하게 하여 3차대전을 유발하게 한다. 양국의 함대들이 출동하여 일촉즉발의 순간에 엑스맨팀이 도착을 한다.

찰스의 초능력으로 가까스로 전쟁을 막아 놓지만 인간을 믿을수 없다며 인간들이 쏘은 미사일을 초능력으로 되돌려 주려한다. 이에 젊은 군인들이 이유도 없이 죽게 된다며 찰스는 막는다. 간신히 전쟁은 막았지만 그 과정에 부상을 입은 찰스와 이를 인간의 탓으로 돌리는 에릭은 다시 한번 부딪힌다.결국 에릭은 자신의 따를자를 부르고 기존 엠마를 비롯한 3인과 엔젤, 미스틱이 따라간다. 미스틱은 왜 에릭을 택했을까?