1901년 10월 일본 홍도회(弘道會) 부산지부에서 설치한 것이며, 1911년 5월 사립 부산교육회에서 이 도서관을 승계, 운영하였고, 1919년 4월부산부(釜山府)로 이관되어 공립도서관으로 발족하였다.
1952년 6월 부산시교육위원회로 이관, 1963년 8월에 부전동에 건물을 신축, 이전하였다. 1968년 11월에 동래분관을, 1976년 1월에 수정분관을 각각 설립하였다. 1982년 8월 17일 현위치로 이전하여 오늘에 이르고 있다.
1901년 당시 장서수는 5,000여권, 광복 이전까지는 2만2413권이었다. 1998년 10월 현재 장서수는 40만여권이며, 그 가운데에는 향토사관계의 귀중한 자료가 많이 소장되어 있다. 특수 시설로는 성씨자료실·어학실·시청각실·이동자동차문고·인쇄 및 발간실이 있다.
도서관은 먼저 개가제(開架制)에 의한 자료열람방식이며, 이용자 중심으로 운영되고 있다. 또한 이동자동차문고 운영, 바다도서관을 설치하여 도서관 봉사활동 범위를 확산하며 독서인구 저변확대를 위하여 독서회를 조직, 무료관외대출을 하며, 그 회원들로 하여금 도서관 홍보요원으로서의 구실을 하도록 하고 있다.
초·중학생의 독서지도를 위한 겨울독서교실과 여름독서교실, 일일독서교실을 운영하며 주부교양대학, 예절 및 서예교실 운영, 음악감상회, 영화 및 비디오 상영, 음악연주회 개최 등의 프로그램을 실시하고 일상생활에 필요한 지식, 각종 의문사항에 대하여 정보를 제공하는 시민백과의 운영, 기타 어학실 운영, 시청각실의 시민에 대한 장소제공 등을 하고 있다.
이 도서관에서 발행한 주요 간행물은 『장서목록-고서』(1965)·『부산시립도서관약사(釜山市立圖書館略史)』·『장서목록-해방전 일본어도서편』(1970)·『도서해제(圖書解題)』 등이 있다.