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