東京から派遣されたワシリイ田手伝教者が1878年に戸部町と花咲町に講義所を開いたことに横浜正教会の歴史の始まりがある。
翌年には保土ヶ谷で講義が行われ、1884年には、太田町に講義所が設置されて、北川伝教者や小林伝教者の活躍があった。
1889年には講義所を福富町に移した後に、会堂を通称税関山に建てた。現在この場所は、野毛山公園の花壇となっている。会堂の成聖式には、聖ニコライ大主教をはじめ、多くの聖職者や信徒たちが出席した。
会堂建設をこの場所に決めたのは眺めがよく、横浜港に入る船から教会の屋根の十字架がよくみえるからであった。しかしここは不便であったことから、1893年に太田町に移転した。
1923年の関東大震災のために会堂は全壊。
試練のなかにも新しい聖堂を建てようという動きが起こって、1935年に中区山手の地蔵坂上に聖堂が建設された。そのころは、亡命ロシア人たちの参加者が多く、聖歌もスラブ語と日本語で歌われた。第二次大戦に疎開などによって信徒たちが離散すると、一時はロシア人信徒たちによって、教会が守られることもあった。
その後、ロシア人信徒たちが他国に移り住むようになると、日本人信徒が後をついで盛んに教会活動に参加するようになった。
1980年には聖堂を現在の神奈川区松が丘に新しく建設した。
聖堂のなかのイコノスタスは、セルギイ・ポサド修道院で制作され、1984年に設置された。