우리나라 최초의 근대식 병원인 제중원(濟衆院)에 부설된 제중원교회가 그 전신이다. 제중원교회는 선교사 알렌(Allen, H. N., 주1 및 헤론(Heron, J. W., 惠論) 부부와 메리 스크랜턴(Scranton, M. F. B., 施蘭敦) 등에 의하여 1887년(고종 24) 11월 21일에 설립되었다.
처음에는 구리개(銅峴)(현, 을지로1가)에 위치해 있었으나 1904년 9월 제중원이 남대문 밖 복숭아골(현, 중구 양동)로 이전되면서 교회도 따라서 옮기게 되었고, 이름도 남대문밖교회 혹은 남문밖교회로 불렸다.
미국 북장로회 선교사인 언더우드(Underwood, H. G., 주2가 관리를 맡았으며, 병원 책임자였던 에비슨(Avison, O. R., 魚丕信)이 지원하였다. 1907년 병원 안에 별도의 예배당을 마련하였다. 1909년 11월 당회를 조직하여 장로교 주3를 갖춘 조직 교회가 되었다. 1910년 12월에는 세브란스(Severance, L. H.)의 기부금으로 새로운 교회당을 세웠고, 1912년에는 초대 담임 목사는 박정찬(朴禎燦)이 맡았다.
1919년에는 3·1운동에 참여한 집사 이갑성(李甲成), 조사(助師) 함태영(咸台永) 등은 3년 이상의 옥고를 치렀다. 특히 이갑성은 청년 대표로 민족 대표 33인에 참가하였다. 1924년 12월, 제3대 목사로 취임한 김익두(金益斗)는 유명한 부흥 설교가로서 교회의 발전에 많은 공헌을 하였으나 주4 시비로 물의를 빚기도 하였다.
또한 1934년에 취임한 김영주(金英珠)는 ‘창세기 모세 저작설 부인 사건’을 일으켜 총회에서 이단 여부를 조사받기도 하였으나, 일제강점기 말기에 신사 주5와 조선혁신교단의 설립으로 한국 교회가 위기에 처하자 혁신교단의 의장인 전필순(全弼淳)의 주6을 요구하는 등 강력히 저항하였다.
1944년에는 김치선(金致善)이 제6대 목사로 부임하여 1953년까지 목회 활동을 하면서 ‘삼백만 부흥 운동’을 전개하였고, 현 대한신학교의 전신인 야간신학원도 설립하였다. 6·25 전쟁 때에는 교회가 완전히 파괴되었으며 주7 후 다시 지어졌는데, 이때를 전후하여 당시 집사이던 박태선(朴泰善)의 신앙 노선에 문제가 제기되어 이단 시비를 불러일으켰다.
1954년 9월에는 미국에서 독립운동과 한인교회 활동을 벌이던 김태묵(金泰默)이 부임하여 교회당 건축에 힘을 기울였고, 1957년부터 1979년까지는 배명준(裵明俊)이 제8대 목사로 부임하여 교회 발전에 큰 기여를 하였다.
박정찬 이후 2013년 현재 손윤탁 목사에 이르기까지 13명의 한국인 목사들이 이끌어 온 남대문교회는 교회의 대형화보다는 새 교회 개척에 정성을 쏟으며 공덕(孔德) · 행화정(杏花亭) · 삼판통 · 청량리중앙교회 · 해방촌교회를 세웠다. 최근에는 맹인교회인 애능중앙교회를 설립하였다.
1979년에는 교회의 역사를 정리한 『남대문교회사』를 편찬하였고, 1987년에는 창립 100주년을 맞았다.
2008년부터 1885년 6월 21일 알랜의 집에서 드린 외국인 선교사들의 예배를 교회의 기점으로 잡았으며 이에 근거해 2015년 6월에 130주년 기념식을 했다.