해병대사령부에 교회 창설의 기운이 태동한 것은 해병대가 6.25전쟁 당시 중공군의 개입으로 인해 진해로 철수하여 부대를 재편하면서 차후 작전을 위한 전투태세를 갖추고 있을 때였다. 당시 해병대사령부 참모장으로 근무하던 김대식 중령은 해병대에 구원의 기쁜 소식이 전해지길 간절히 원하고 있었다. 그는 군인이 신앙으로 무장하면 더욱 투철한 군인정신을 갖게 된다는 것을 잘 알고 있었기에 사령부에 교회를 세우고자 했다. 소위 신앙 전력화의 필요성을 절감한 김대식 중령은 당시 해군통제부교회에서 시무하던 박창번 목사를 초청하여 해병대사령부에서 예배를 드리려고 추진했다.

이와 같은 노력으로 1951년 3월 12일 당시 해병대사령부가 임시 주둔하고 있던 진해여자고등학교 강당에서 해병대사령부교회 창설 예배를 드렸다. 사회는 신학교를 졸업하고 정훈감실에서 근무하던 김동선 군무원, 기도는 참모장 김대식 중령(장로), 설교는 박창번 목사(해군통제부교회 담임, 군무원)가 담당하였고 60여 명의 교인이 예배에 참석하였다. 이처럼 해병대사령부교회는 해병대사령부 조직도에 군목실이 설치되기 이전에 먼저 설립되었다. 

그 이후 해병대 군목업무의 기초작업을 위해 초빙된 장창덕 목사가 해병대사령부교회에 시무하게 되었다. 1951년 4월 장창덕 목사의 사회와 설교, 김동선 문관(군무원)의 기도와 독창으로 60여 명이 참석한 가운데 두 번째 주일예배를 드렸다. 4월 15일 해병대 창설기념일에 장충단 해군 묘지에서 전장병이 참석한 가운데 장창덕 목사가 해병대 전몰장병을 위한 추도예배를 집례하였다. 최초의 해병대 전몰장병 추도예배였다.

장창덕 목사는 군종업무를 위해 일할 일꾼을 얻는 것이 급선무라고 생각했다. 그해 2월 조선신학교 출신 신성국 소위와 반병섭 소위가 7대대와 독립 5대대에서 정훈업무를 담당하고 있는 것을 확인하고 신학교 출신인 이 두 사람이 우선적으로 군종업무를 겸무하도록 건의하여 재가를 얻었다. 같은 해 4월 5일 이 두 명의 정훈장교가 군종업무만 전담할 수 있도록 군종장교로 전과 발령을 냈다. 한편 그는 군종목사를 모집해서 전방부대에 종군하도록 하는 계획을 수립했고, 마침내 4명의 군목을 모집하여 해병대 제1기 특과 사관후보생으로 해병학교에서 훈련을 받게 하였다. 군종업무의 기초를 닦은 장창덕 목사는 개인 사정으로 해병대사령부를 떠날 때까지 정훈월보에 글을 기고하는 등 문서 선교에도 힘쓰면서 군종업무 발전을 위해 노력했다.

1951년 5월 장창덕 목사 후임으로 송흥국 목사가 부임하였다. 송흥국 목사는 1951년 5월 27일 창설된 해병대사령부 초대 군목실장-장창덕 목사를 포함할 경우 제2대 군목실장-이 되었다. 제2대 해군정훈감을 역임한 감리교 목사인 그는 제도화된 군목실 기구를 마련하고 군종실장 예하에 행정과장과 대원 3명을 두고 업무를 시작했다. 정훈감실에서 근무하던 신학교 출신의 김동선 문관(군무원)이 군종실의 초대 행정과장으로 전입했다. 당시 해병대사령부가 진해에서 부산 용두산으로 이동한 직후라서 적당한 교회 시설이 없었고 제대로 예배를 드릴 수도 없었다. 따라서 송흥국 군목실장은 과업 정렬 시 별도의 시간을 할당받아 정신교육을 하면서 동시에 복음을 전했다.

해병대사령부교회는 해병대 최초의 군종장교인 박창번 군목(대위)이 부임하면서 다시 정상 궤도에 올랐다. 1951년 8월 27일 해병대사령부로 발령을 받고 9월에 군종실장으로 취임한 그는 해병대사령부교회의 발전을 위한 업무를 서두르기 시작했다. 박창번 목사는 1952년 4월 경부터 사령부 강당을 예배 장소로 정하여 교회 활동을 재개하였다. 주일예배에는 영외거주자들이 가족 동반으로 참석하였고, 수요예배와 주일 저녁예배에는 주로 사령부에 근무하는 해병대원들이 참석하였다.

당시 부산에 주둔하고 있던 해병대사령부에는 별도의 교회 건물이 없었다. 박창번 군목이 부산의 용두산 산정에 사령부교회를 신축하고, 1952년 5월 4일 해병대 창설 4주년 기념 및 교회 준공예배를 드렸다. 이 예배에는 이승만 대통령 부처와 부통령, 심계원장, 김일환 국방차관, 손원일 해군총참모장, 신현준 해병대사령관을 비롯한 장성들과 일반 교우가 참석하여 교회에 앉을 자리가 없을 정도였다. 박창번 군목의 사회로 예배를 시작해서, 정달빈 해군 군목실장의 ‘조국의 위기’란 제목의 설교, 성가대의 ‘할렐루야’ 찬양, 김천애 여사의 ‘저 생명 시냇가에’ 특송 후, 부통령 함태영 목사의 축도로 준공예배를 마쳤다.

박창번 군목은 사령부교회를 목회하면서 6.25전쟁으로 인해 부상을 입은 상이군인을 위한 기술교도소를 설치하여 운영하였다. 그는 기술교도소의 부속교회인 일맥교회 창설과 군종업무 체계를 확립하는 데에 온 힘을 기울였다. 그는 제6대 군목실장으로 해병대사령부교회에 다시 부임하였으며, 전도문고 발간에 힘을 기울이며 전택부 선생이 쓴 「정의와 자유와 개화사상」이란 책자를 출판했다.

1952년 10월 27일 박창선 군목이 제3대 해병대사령부 군목실장으로 취임하였다. 주일예배에는 60명 정도의 교인이 모였고, 인근에 위치한 덕성여고 학생을 위주로 구성된 성가대가 함께 했다. 성례전은 연 2회 베풀어졌고, 박창선 군목이 당시 해병대사령관 김석범 장군을 전도하여 세례식을 거행하기도 했다. 박창선 군목은 영창 방문, 내무실 방문, 마산 형무소 방문도 하였으며 박동선 문관이 그 일을 도왔다.

그는 군종 예산 획득과 해병 전도문고 발간에 힘을 기울였다. 해병대 자체에서 예산을 획득해서 「기독교 신앙문답」 1,500부, 「군목 설교집」, 「가톨릭 신앙의 기초」, 「기독교 신앙원리」, 「행복의 길」 등 해병 전도문고 5집을 발행하였다. 또한 탈영병 구제를 위해 자수기간을 설정하도록 권유해서 탈영병들이 다시 원대복귀해서 근무할 수 있도록 주선하고 그들을 도왔다.

1953년 11월 1일 해병대사령부교회에서 제2대 해병대사령관 김석범 소장의 취임예배가 있었으며, 1954년 성탄절에는 박창선 군목의 집례로 김석범 사령관, 박정오 소령, 박동열 소령 등 10명이 세례를 받고 8명이 학습을 받는 세례식이 있었다. 김석범 사령관은 매주일 사령부 교회에 출석하여 예배를 드리며 장병들의 신앙 무장을 권고하고 신앙의 해병이 되기를 원했다. 김석범 사령관은 기독교인이 된 경로를 다음과 같이 회고했다.

내가 기독교를 믿게 된 것은 해군의 역사와 때를 같이 하였다. (중략) 1951년 9월에 서부전선 임진강 지구에 출동하여 전투단 단장으로 부임하였다. 그후 나는 일요일이면 교회에 나가도록 노력하였고 또한 목사님이 하는 일에 이해를 하게 되었다. 당시 전투단의 군목이었던 목사님은 장병들에게 일요일 예배시간을 통해 유익한 설교는 물론 전 장병의 위문이며 전사자의 장례식도 종교의식으로 거행하여 고인의 명복을 빌고 또한 가족들과 전우들에게까지 기도를 올리었던 것이다. 휴전협상 중이라고는 하지만 매일 밤같이 벌어지던 적의 야간전투에 있어서는 밤중 1시였건만 군목은 전투지휘소였던 작전실에 나타나 장병들의 노고를 위로하면서 교전 중에 있는 일선 장병들의 무운을 빌며 기도를 하였던 것이다. 나는 지금도 목사님이 상황도를 보고나서 기도하시던 것이 잊혀지지 아니한다. 이때에 목사님이 와 있던 것이 사단장이나 군단장이 옆에 있는 것보다 더 반갑고 의지하고 안정감을 느꼈던 것이다. 전투단장을 마치고 부산 사령부로 내려와 (중략) 사령관직을 신현준 사령관으로부터 인계받고 첫째 사업으로 사령관실 바로 옆에 있던 대강당을 교회로 겸용토록 하고 예하 장병들에게 교회에 나갈 것을 권유하였고 나 자신도 매주 가족들과 같이 교회에 나갔던 것이다. 그리하여 당시의 군목실장 박창선 목사님으로부터 세례를 받고 교인이 되었다. 

박창선 군목 재임 기간 중 용두산 산마루에 해병대사령부교회가 신축되었다. 이 교회는 군용 퀀셋(Quonset) 2동을 연결하고 앞에 종각을 세운 것으로 피난 중인 군인교회로 훌륭한 것이었다. 1954년 4월에 착공하여 1954년 6월 10일에 완공되었다. 미 해병 고문관들이 제단용 십자가와 촛대를 기증하였고, 어느 미군 부대에서는 피아노를 기증하였다. 하지만 이 교회는 1954년 12월 11일 발생한 용두산 일대의 대화재로 인해 소실되었다.

1955년 2월 20일 유영근 군목이 박창선 군목의 후임으로 화재로 전소한 해병대사령부교회에 부임하였다. 그러나 정부 환도에 뒤이어 해병대사령부와 함께 교회도 서울로 올라오게 되었다. 한동안 사령부 브리핑실을 예배장소로 사용하다가, 수송대 옆의 퀀셋 교회가 마련되었다. 당시 해병대사령관 김석범 장군의 배려로 만들어진 이 교회에서 환도기념예배 및 해병대 군종업무(교회) 창설 6주년 기념예배를 드렸다. 이 예배는 백낙준 박사의 설교, 서울시장의 축사, 함태영 부통령의 축도로 진행되었고, 김석범 해병대사령관의 은혜의 말씀이 있었다. 1956년 4월 15일 해병대 창설 기념예배 후에는 강기천 대령 외 14명이 세례를 받았다.

강기천 대령은 후에 제7대 해병대사령관이 되었다. 해병대는 가톨릭 신자인 제1대 사령관 신현준 장군을 제외하고, 제2대 김석범 사령관으로부터 제3대 김대식, 제4대 김성은, 제5대 김성은, 제6대 공정식, 제7대 강기천 사령관에 이르기까지 모두 개신교 신자였다. 초창기 해병대사령관들이 기독교인이었다는 사실을 고려해 볼 때, 창설 초기 해병대의 모습 가운데 기독교적인 분위기가 형성되었음을 유추해 볼 수 있다.

김석범 사령관은 용산의 언덕 지대에 자리잡은 해병대사령부 지대의 가장 높은 곳을 교회 신축부지로 선정하였다. 사령관의 적극적 협조로 박영근 군목은 군용 퀀셋 2동을 연결한 십자가형 교회를 마련하고 내부시설도 아담하게 장식하였다. 내부시설은 당시 해병대교육단교회와 합병된 해병대보급정비단교회의 내부시설 대부분을 그대로 옮겨 놓은 것이었다. 해병대보급정비단교회는 미 해병대의 교회시설을 그대로 인수한 것이었기에 그 설비가 매우 훌륭한 것이었다. 매주 주일예배에는 70명 내외의 교인이 참석하였고, 신우회 주최로 주일 저녁예배도 드렸다. 이 신우회는 환도 직후 1955년 4월경 신앙이 돈독한 군종감실 신모 하사관에 의해 발족한 것으로, 사병들을 중심으로 이룩된 3군 최초의 신우회였을 것으로 생각된다. 1956년 2월 1일 육·해·공군의 신우회원을 초청하여 제1회 3군 연합 좌담회를 사령부 식당에서 개최했다.

유영근 군목은 문서선교에 관심을 갖고 신앙잡지로 「불기둥」을 발행해서 사병들의 종교생활에 도움을 주었으며 전방 초소와 벙커에도 전달해서 장병들이 책을 벗하도록 했다. 처음 발행 시에는 예산도 없고 인쇄계획에도 반영이 되지 않아서 군목들이 그림을 그리고 무료 원고를 구해서 편집하였으며, 7호부터 예산이 반영돼서 1973년 해병대사령부가 해체될 때까지 계속 발행되었다. 

유영근 군목 후임으로 박창번 군목이 1956년 6월 18일 취임하였다. 모든 업무가 예전처럼 순조롭게 진행되었다. 박창번 군목이 원에 의해 제대하고 1957년 4월 13일 전덕성 군목이 취임하였다. 1958년 5월 4일 해병대 창설 9주년 기념예배와 교회 창설 기념예배를 드렸다. 홍현설 박사가 이 예배에서 설교를 하였다.

전덕성 군목의 재임 기간 중 해병대사령부교회가 퀀셋 구조에서 콘크리트 구조의 영구적 건물로 신축되었다. 이 교회는 전덕성 군목의 노력과 제3대 해병대사령관 김대식 장군의 의도에 따라 국가 예산으로 건축되었다.

14,098,353환 상당의 이 교회는 상전기업주식회사(대표 김덕준)가 1959년 11월 14일 착공하여 1959년 12월 31일 준공하였다. 드디어 건평 60평의 아담한 시멘트 콘크리트 교회가 신축되었다. 내부도 잘 설비되고 하몬드 오르간까지 설치되었다. 

해병대의 역사이기도 한 해병대사령부초대교회에는 전투에 나서면 한 치의 물러섬 없이 적과 맞서 싸웠던 ‘해병대 DNA’를 엿볼 수 있는 뜻깊은 구조물도 있다. 예배당 중앙에 자리 잡은 커다란 십자가가 그것이다. 소박한 느낌의 이 십자가는 1951년 해병대 제1연대가 북한군에 맞서 혈전 끝에 탈환한 강원도 양구군 도솔산에서 자란 고로쇠나무로 만들어졌다. 700여 명의 전·사상자를 내면서도 도솔산 고지를 탈환했던 산악 대공방전으로써 해병대 전투사에 길이 남는 작전 가운데 하나다. 해병대사령부초대교회는 조국을 위해 목숨을 바친 해병대 전우들의 고귀한 희생을 잊지 않기 위해 도솔산에서 나무를 가져와 십자가를 만들었다.

1961년 5월 29일 전덕성 군목의 후임으로 송창설 군목이 해병대사령부교회에 부임하였다. 기독장교회의 움직임이 활발해지면서 교회는 다시금 활기를 띄기 시작했다. 기독장교회 회장 이봉출 대령은 매주일예배에 다른 기독장교회 멤버들과 함께 가족동반으로 참석하였고, 문희석 대령은 문교부장관이 된 이후에도 줄곧 이 교회에 출석했다. 주일예배 후 오후에는 해병막사에서 예배가 거행되었고 영창 방문도 정기적으로 행해졌다.

1962년 4월 17일 김광덕 군목이 송창설 군목의 후임으로 부임하였다. 주일 오전예배는 40~50명이 참석했고, 수요예배는 사정에 따라 간헐적으로 실시하였으며, 영창예배와 막사예배도 계속하였다. 막사에서 드리는 주간 예배에는 70~80명이 모였다.

1963년 11월 12일 김광덕 군목 후임으로 한기원 군목이 부임하였다. 30여 명의 기독장교회 회원들이 주간 성경공부, 월간 초빙강연, 구제사업 등을 하였다. 신우회는 40여 명의 회원이 주간 성경공부, 헌신예배 등을 하였다. 해병대사령부교회 교인은 120명 재적인원에 40명 내외로 예배에 출석하였다.

1964년 2월 9일 해병대사령부교회에서 공정식 장군의 사령관 취임 예배를 거행하였다. 해병대사령부 기독장교회는 회장 이봉출 준장, 부회장 오종해 대령, 총무 임경섭 중령, 부총무 임춘하 대위, 홍경석 대위가 선출되었다. 신우회도 40여 명의 회원이 가입하여 활동했다.

이종영 군목이 성경연구반 운영을 계속하였으며 사고 방지를 위해 수감자와 퇴창자 선도에 힘을 기울였다. 1968년 10월 21일 손흥수 군목이 이종영 군목 후임으로 부임한 이후 막사예배를 실시하였다.

1971년 7월 12일 김용원 군목이 손흥수 군목 후임으로 부임한 후 기독장교회 가족들이 사령부 교회에 출석해서 예배를 드리게 되면서 매월 둘째 주일에는 기독장교회 헌신예배로 드렸다. 1971년 12월 9일 교도소 부흥회를 실시한 후 53명에게 세례를 주었고, 1971년 10월 20일 지명관 덕성여대 교수를 초빙하여 교양강좌를 개최하였다.

1972년 2월 15일 주계명 군목이 김용원 군목 후임으로 부임한 후, 1972년 6월 21일부터 23일까지 무의탁사병 위로회를 실시하였고, 1973년에는 보호사병 위로회를 실시하였다. 1972년 2월 30일 교도소 수감자 30명에게 세례를 주었고, Wilson 박사(Billy Graham 목사 일행)를 강사로 종교강연회를 하였으며, 6월 6일 하사관들을 인솔하여 가나안 농군학교를 견학시키고 새마을 정신을 고취시켰다.

1973년 10월 10일 해군부대 기구 개편으로 해병대사령부 군종업무는 해군본부 군종감실로 폐합되었다. 그동안 광석교회, 영락교회, 마르다교회, 보성여고, 켄디컬 성가대, 순복음중앙교회, 서소문교회, 개혁교회, 응암교회, 영은교회, 기독교학생선교회, 영등포감리교회, 문화촌교회, 성만여상, 용산제1교회, 산돌교회, 서울예고, YWCA Y-Teen, 청파성결교회, 신설동교회, OCU부인회 등이 군목을 도와 교도소 수감자들을 위문하였다.

아래 사진은 서울 탈환 이후 용산에 세워진 해병대사령부교회(현 해병대사령부 초대교회)의 모습이다. 현재 해병대사령부 초대교회는 최초 설립 당시의 원형을 그대로 중수 복원하였다.