イエスの処刑後間もなくエルサレムで活動を再開した人々が最初のキリスト教徒であり、その信仰がキリスト教であるが、この段階での「キリスト教」はあくまでもユダヤ教の一分派であり、「ユダヤ教イエス派の運動」や「ユダヤ教のナザレ派」などと呼んだ方が誤解が無いとされる[18][19]。本記事では煩瑣を避けるため鍵括弧で括り「キリスト教」と表記する。これは財産共有制の共同生活を行う共同体であり、ペトロを筆頭とする「十二人」と呼ばれる弟子達が中心となって主流派を構成した[20]。また、当時エルサレムには古くから住むアラム語を話すユダヤ人の他に、周辺地域から再移住したギリシア語を話すユダヤ人達も住んでいた。このようなギリシア語を話すユダヤ人達はヘレニストと呼ばれた。この「ユダヤ教徒のヘレニスト」の中から、エルサレムの共同体へ参加する人々があり、これが「キリスト教徒のヘレニスト」となっていく[21]。

エルサレムの共同体の参加人数は増え続け、次第に財産共有制や全員集まっての共同生活が物理的に不可能になっていった。このため自宅に居住する者達が増え、共同体への寄付は各人の裁量に任されるようになっていったと考えられる[22]。また、寄付する資産の無い貧困者の参加の増大によって共同生活の財源の問題も現れ始めたと考えられる。これらによって、共同生活への参加は強く要求されなくなり、完全な団体生活を送らなくても共同体の仲間となることができるようになった。神学博士の加藤隆は、この段階以後を「エルサレム教会」と呼んでいる[22]。次第に教会の組織化も図られ、洗礼、癒やし、悪霊払いに加え、外部の人々への食事の供与も行われるようになった。このような実務を担当するために「執事」職が設けられた[17]。最初の執事はヘレニストであったという[17]。
ステファノの処刑詳細は「ステファノ」および「ヘレニスト」を参照ステファノ
その名前が明らかにギリシャ風であることからも分かるように、初代教会において、彼はヘレニストの代表であった。彼はファリサイ派によって石打ちの刑にされるが、ジャン・ダニエルーはこの殉教の裏側にキリスト教内部のヘレニストとヘブライストの立場の違いを見ている[23]。図はイタリアバロックのボローニャ派に属するジャコモ・カヴェドーネ (en:Giacomo Cavedone) の作品

ペトロを筆頭とする「十二人」を中心としたアラム語を話す教会の主流派グループに対し、ヘレニスト達はステファノを筆頭とした「七人」を中心としていた[21]。この両者は（『使徒行伝』の伝承を信ずるならば）、共同体内部における食事の配給の不公平を切っ掛けに対立を始めた[21]。これは実際には文化的、教理的な根深い対立が表面化したものであろうと考えられる[21]。特に（ユダヤ教の）神殿や祭儀の権威に対しヘレニストの間から批判の声が強まると波紋が大きくなり、執事であったステファノがエルサレムの大祭司に逮捕される事態に発展した[21][17]。ステファノはその場でユダヤ教の神殿中心の教義を強く批判したためユダヤ教徒各派の激しい怒りを招き、石打ちの刑によって処刑された[21][17]。

この事件を切っ掛けに、「キリスト教」のヘレニストグループはユダヤ当局による迫害の対象となりエルサレムを追われた。一方で主流派はそのままエルサレムに留まった[21]。しかし、エルサレムから離れたヘレニスト達はサマリアや地中海沿岸の各都市など、ユダヤ当局の追及の手が及ばない地域で活発な伝道を行うようになり、「キリスト教」はエルサレム周囲のみならず、各地の都市に広まるようになった[24]。
改宗者パウロパウロ
ヴァランタン・ド・ブーローニュもしくはニコラ・トゥルニエによる1620年ごろの作。パウロはキリスト教を言語化し、神学的説明を加えた。これは後代の信仰理解に決定的影響を与えるものであった詳細は「パウロ」を参照

キリスト教の最初の数十年間で最も重要な人物の一人がパウロである。パウロは西暦1世紀の初め、イスラエルの外に住むユダヤ人ディアスポラの家庭に生まれた。出身地はキリキアにあるギリシア語圏の都市タルソスである[25]。パウロは当初、熱心なユダヤ教徒としてイエスをユダヤ人のメシア（キリスト）として崇める人々を迫害し、ステファノを石打ちに処した活動家の一人でもあった[25]。キリスト教の伝説では、パウロがエルサレムからダマスカスへ向かう途中、「復活」したイエスに出会い「キリスト教徒」への迫害をやめ、異邦人に福音を伝えるように呼びかけられたことで回心したとされる[25]。パウロはその後、アラビア[* 3]で伝道を行い、数年の後、エルサレムでペトロやヤコブと接触を持った。これによってエルサレム教会の指導者達と知己を得たパウロは、その直後からシリア、キリキア、キプロス島、アナトリア中央部からエーゲ海地方などを周り、各地で教会を作ったとされる[26]。
パウロとユダヤ教

パウロの伝道は異邦人に対しても積極的に行われたため、非ユダヤ人の「キリスト教徒」が多数生まれることになった。このことは後に大きな論争を引き起こすことになる。前述したとおり、この時代の「キリスト教」はなおユダヤ教の一形態であった。最初の数十年間、「キリスト教徒」のほとんどはユダヤ人であり、各地にあるシナゴーグが「キリスト教」普及のための拠点となった。パウロ自身も、新たな都市ではシナゴーグで福音を伝えたのであり、「キリスト教徒」となることが「イスラエルの民」への帰属を意味すると信じていた[26]。

パウロはキリスト教思想において最も重要な人物の一人とされ、ユダヤ教からイエスによって解放されたとする見解がルター以来主流であった[27]。しかし、トロクメによれば、パウロ自身の意識ではユダヤの思想家であり、ユダヤ教内部の論争に関わっていたという[27]。またトロクメは、パウロを「キリスト教の創始者」と考えることを批判し、この考えがイエスを「ユダヤ教の改革者」という誤った位置づけに貶めるものだという。トロクメはパウロの思想がアウグスティヌス以前は正確に理解されているとは必ずしも言えないこと、中世の神学でもあまり重視されていないことを挙げ、パウロにキリスト教における中心的な地位を与えたのはルネサンスと宗教改革であると述べている[28]。
異邦人の改宗

十数年にわたり伝道者として活動した後、パウロはキプロス出身のユダヤ人バルナバと、ギリシア人の改宗者テトスとともにエルサレムを訪れた。そこで、ユダヤ・「キリスト教徒」との間に異邦人の改宗者を巡って激しい議論が繰り広げられた。