충무교회는 호주 선교사 아담슨(Andrew Adamson)에 의해 1905년 설립되었다. 당시는 대화정교회로 불리었다. 충무교회는 진명유치원-진명야학교-진명강습소와 관련을 맺으며 발전하였는데, 이교회와 학교의 출신들로는 윤이상, 유치환, 유치진, 박경리, 김춘수 등이 있다.
통영지역은 호주 선교사 무어(Miss Elizabeth S. Moore)에 의해 1894년 무렵 기독교가 전해졌다. 통영군 용남면 출신인 김치몽이 이때 기독교를 신종하였지만 곧 고향을 떠나 부산에 정착하였다.
이후 아담슨의 전도로 1902년 봄 통영군에 동항리교회(욕지도)가 세워졌다. 당시 박명출·박인건·이영백·최명언 등 동항리의 초기 교인들은 마을 사람들의 위협에도 불구하고 예배당을 세웠다고 한다.
통영의 중심지에도 교회가 세워졌는데, 이것이 1905년에 설립된 대화정교회(현 충무교회)이다. 당시 아담슨 선교사의 전도로 권희순이 기독교를 믿고 그의 집에서 교회를 시작했다. 그 후 대화정교회는 통영 상주 선교사들과 관계를 맺으며 발전하였다. 그 선교사들은 교회를 인도하는 한편 부근 대화정 269번지에 건물 3개 동을 지어 진명유치원과 진명야학교 그리고 진명강습소를 시작하였는데, 이것이 통영 최초의 근대식 교육기관이었다. 여선교사인 스키너(Miss Amy G. M. Skinner)는 1914년에 내한해1940년까지 통영지역의 교육 선교에 나서 지역사회에 큰 영향을 미쳤다.
그 외에 의료선교사 테일러(William Taylor)는 지금의 보건소와 같은 건강관리소를 설치하고 지역민들에게 진료를 실시하여 큰 반향을 일으켰다. 특히 섬사람들을 위해 호주의 교인들이 기부한 모터보트를 타고 순회하며 환자들을 돌보았다.
1956년 3월 18일 충무교회로 명칭을 변경했고, 1983년 새로운 현대식 건물을 지었다. 교회 입구에는 작곡가 윤이상, 시인 유치환, 극작가 유치진, 소설가 박경리, 시인 김춘수 등이 충무교회와 진명학교에서 어린 시절을 보냈음을 밝히는 안내판이 설치되어 있다.