1894년 미국 북장로교 선교사 모삼열(牟三悅, Moore,S.F.)의 조사(助事) 김영옥(金泳玉)과 천광실(千光實)이 시가전도에 힘쓴 결과 얻어진 신도들로 교회가 시작되었다. 이듬해 미국 북장로교 선교사 이길함(李吉咸, Lee Graham)과 조사 서상륜(徐相崙)의 지도로 이미 전도받은 신도들이 회동하여 현 위치에 있었던 초가 한채를 매입하여 예배처소로 삼았다. 이 곳을 중심으로 종로5가 일대의 전도에 힘쓴 결과 교회가 크게 발전하게 되었다.
1900년 미국 북장로교 선교사인 게일(Gale,J.S., 奇一)이 담임목사로 시무하기 시작하여 1,000여 명이 모이는 당시 가장 큰 교회로 육성하였다. 1904년에 조사 고찬익(高燦益)을 장로로 장립하여 처음으로 당회(堂會)가 조직되었다. 1907년에는 1, 200석의 예배당을 건축하였다. 연동교회가 이처럼 급성장한 데에는 유능한 지도자들이 많았던 것이 그 이유 중의 하나였다. 게일 목사와 고찬익 장로를 비롯하여 독립협회 회원들, 특히 이상재(李商在), 김정식(金貞植), 이원긍(李源兢), 홍재기(洪在箕), 유성준(兪星濬), 박승봉(朴勝鳳), 민준호(閔濬鎬) 등이 교회를 위해 크게 활약하였다.
한편, 1894년 현 연못골 대지를 미국 북장로교에서 매입하여 선교부 기지로 사용하면서 경신(儆新)과 정신(貞信)의 두 중등학교가 연동교회 옆에 자리잡게 되었고, 그 결과 연동교회는 교육적이며 지성적인 귀족교회로 알려졌다. 1919년 3 · 1운동 당시 연동교회는 최남선(崔南善), 이갑성(李甲成), 이상재, 함태영(咸台永), 신(辛)마리아, 신의경(辛義卿), 김필례(金弼禮) 등 민족지도자들의 독립운동의 온상이 되었다. 연동교회의 역대 목사는 게일, 함태영, 전필순(全弼淳), 백이언(白理彦), 김형태(金炯台), 이성희(李聖熙)로 6대를 이어오고 있다.
2009년 현재 2,000여명의 교인이 있다. 유치원 · 청소년학교(야간) · 노인학교를 경영하고, 30여 개의 국내 개척교회를 지원, 해외 선교사를 파송하고 있다.