금융의 수도권 편중 경향을 탈피하고 지방은행으로 하여금 지역사회 개발을 담당하게 하기 위하여 1967년 10월 25일에 설립되었다.
초기에 본점을 부산광역시 동구 범일동에 두고 서울에 2개 점포, 마산(지금의 창원시)에 1개 점포를 둔 것을 시작으로 전국적으로 점포를 늘려나갔다.
한국은행 국고 대리점 업무와 은행업무·외국환업무를 취급하였으며, 특히 외국환업무의 취급량이 증대됨에 따라 이의 신속한 처리와 국제금융시장의 정보수집을 위해 1987년 말 당시 예치환 41개 은행을 포함한 세계 978개 은행과 환거래계약을 체결하였다.
1983년부터 신탁업무, 1985년부터 크레디트카드업무도 취급하며, 전점포의 온라인화가 이루어져, 여·수신업무에 신속과 능률을 기하게 되었다.
1986년 7월 싱가포르 금융시장에서 뱅크론을 도입하였으며, 1987년 4월 전산메인시스템을 IBM으로 전환하였다. 1987년 10월 『부산은행 20년사』를 발간하였으며, 1990년 1월 기업이미지 통일화 계획(CPI)을 도입하였다.
1994년 11월 O.C.R.센타를 설립하였고, 1996년 5월 인터넷 홈페이지를 구축하였으며, 1996년 7월 ALM 전산시스템(SENDERO)을 가동하였고, 10월 종합상담실을 설치, 운영하였다.
2011년 3월 BNK금융지주㈜의 자회사로 편입됨으로써 주식시장에서 상장이 폐지되었다. 2012년 11월 중국 칭다오지점을 개설하였고, 2011년 6월 개설된 호치민 사무소는 현재 지점 전환을 준비 중에 있다. 2015년 현재 국내 점포 271개, 해외점포 1개(중국 칭다오), 해외사무소 1개(베트남 호치민)를 운영하고 있다. 2015년 현재 총자산은 56조 3166억원이며, 임직원은 3800여명에 이른다. 본점은 부산광역시 남구 문현금융로 30(문현동 1231)에 있다.