1935년에서 1951년까지 중국에서 의료선교사로 봉사하다가 공산당의 손에 의해 순교당한 미국인 외과의사 왈레스(William. L. Wallace)를 기념하고 6·25전쟁 직후 낙후되었던 한국의 보건의료 부문에 봉사하기 위하여 미국 남침례교 한국선교회 유지재단에서 세운 병원이다.
1951년 부산시 중구 남포동에 브라이언(Bryan, N. A.)이 진료소를 개설한 뒤 1955년 11월 영도구 영선동에서 침례병원으로 개원하였다. 병원의 설립 목적은 환자 치료와 의료요원 교육, 복음 전도로, 1964년 인턴·레지던트 수련병원으로 지정받았고, 1974년 종합병원으로 개설 허가를 받았다.
1982년에는 종합건강진단센터를 개설하였으며, 1984년 인공신장실을 개설하였고, 1987년에는 첫 심장수술을 실시하였다. 또한 1987년 부산지역에서 가장 낙후된 지역인 연산3동에 지역사회보건사업소를 개설하였고, 1991년도에는 범일동에 지역사회보건사업소를 개설하여 1차보건사업을 중점적으로 지역 주민의 1차보건 및 건강 증진을 도와 주고 있다. 그리고 1991년 5월 31일 암센터를 준공하여 암환자를 치료하는 진료기관으로 성장하게 되었다.
1992년에는 미국 남침례교 한국선교회 유지재단 산하에서 의료법인 기독교한국침례회 의료재단으로 독립법인이 되었다. 같은 해에 응급의료센터를 개소하였고, 1993년에는 병원의 규모가 지속적으로 성장함에 따라 협소한 진료공간, 주차장 문제, 편의시설 및 대기공간 부족 등 환자의 진료 및 요양에 보다 나은 환경을 조성하기 위하여 병원을 신축하기로 하고 남산동에 신축병원 부지를 매입하였다.
1995년 11월 21일 남산동에 침례병원 신축기공식을 가졌고, 1999년 11월 준공하여 이전하였다. 신축병원은 15,000여 평의 대지 위에 600∼800병상을 운영할 수 있도록 본관 지하 2층, 지상 12층 건물과 지상 9층의 주차 건물이 서게 된다. 1998년에는 495병상에 620여 명의 직원이 일하고 있었으며, 내과를 비롯하여 23개의 진료과목이 있었다. 2000년도 550병상으로 허가병상이 증가하였으며, 26개의 진료과목이 있다.
연 외래환자는 560만 명이고, 연 입원환자는 330만 명이며, 수련받은 의사 수는 인턴 450명, 레지던트 782명이다. 침례병원은 기독교정신으로 세워진 병원이어서 매주 수요일 오전 직원들이 예배를 드리며, 매주 일요일 환자들을 위한 예배를 드린다.
환자의 영적 치유를 위해 모든 환자를 방문 상담하고 복음 전도에 힘쓰고 있다. 또한 매월 무의촌지역에 무료 진료를 나가 지역 주민에 대한 계몽과 진료를 담당하는 등 지역사회를 위한 봉사를 소홀히 하지 않고 있다. 의료부족 국가인 방글라데시, 필리핀, 인도, 중국 등을 1년에 4~5회 의료 봉사와 선교를 하여 국내뿐만 아니라 해외에도 복음과 의료를 전파하고 있다.
2017년 7월 경영난으로 폐원하였다.