1882년 조미수호통상조약 체결로 관세 자주권을 확보한 조선 정부는 청국 해관 시스템을 도입하였다. 1883년 일본과의 통상장정을 개정하고 협정관세체제로 전환하면서 인천 · 원산 · 부산에 해관이 창설되었다. 부산해관은 근대적인 무역 제도 하에서 수출 · 수입품에 대한 관세 징수 방안을 마련하기 위해 설립되었다.
1878년 9월 부산두모포진에 해관(수세소)을 설치하고 15~20% 수입세를 부과하였다. 이때는 조선 상인에게만 징세하였는데, 조일수호조규에서 일본과의 무역에 무관세무역을 보장했기 때문이다. 그러나 해관세 수세로 물품 가격이 급등하자 일본측은 해관세가 조약에 위반되었다며 세금을 부과하지 않을 것을 요구하였다. 일본 측의 계속된 철폐 요구로 12월 결국 두모포진 해관은 철폐되었다.
부산해관은 1883년 7월(또는 11월) 3일 본정 2정목(현, 중구 동광동 2가)에서 개청하였다. 1885년 현 부산데파트(중구 중앙대로 29번길 3, 동광동 1가 1) 자리에 목조 2층 청사와 보세창고 1동을 지어 이전하였다.
1907년 부산세관으로 개칭되었으며, 1911년 8월(또는 1910년 11월) 현재 부산본부세관이 위치한 부근에 4층탑이 있는 붉은 벽돌 2층의 새 건물이 준공되었다.
1970년 7월 관세청이 발족하였으며, 1980년 6월 관세청 관하 부산본부세관으로 승격하였다.
청국이 추천한 독일인 묄렌도르프[Möllendorff, 한자이름: 목인덕(穆麟德)]가 통리교섭통상사무아문 협판으로 해관 총책임자인 총세무사를 겸하였다. 1883년 해관 창설과 함께 부산 · 인천 · 원산에 감리가 임명되었으며, 부산항 초대 감리로 1883년 8월 이헌영(李憲永)이 임명되었다. 감리는 해관 감독관 기능을 하였다.
해관 운영은 통리교섭통상사무아문이 총세무사를 통해 각항 세무사(해관장)에게 지시하는 것과, 통리교섭통상사무아문이 각항 감리를 통해 세무사에게 지시하는 이원적인 체계였다. 해관에 대한 감리의 영향력은 해관의 편의를 제공하는 정도로 제한적이었다.
해관장은 1대 Lovatt(영국), 2대 Piry(프랑스), 3대 Hunt(영국) 등이다. 1906년 7대 야마오카 요시고로[山岡義五郞]부터 1945년까지는 일본인 세관장이었다. 1883년 부산해관 개청 당시에는 서양인 외에 중국인, 일본인도 근무하였다.
해관 직제는 징세부와 해무부로, 징세부는 다시 내반과 외반으로 나누어졌다. 내반에는 방판 · 서기 · 잡원, 외반에는 총순 · 검사관 · 검사관보 · 검사관시보 · 감시 · 잡원이 있었다. 해무부는 항무국[理船廳]과 항무장이 있었다.
해관장은 관세, 재정수입, 회계, 직원 실태, 관내 동향, 밀무역, 외국 선박, 재산 등 상황을 총세무사에게 보고하였다. 해관은 수출입 관리, 관세 징수의 주 업무 외에 선박 입출항, 보세창고, 개항장 관리, 어장 인허가 등 다양한 업무를 담당하였다.
부산본부세관은 1996년 7월 부산경남지역본부세관으로 승격하였다. 청사는 중구 충장대로 20(중앙동 4가 17)에 위치한다. 통관, 심사, 조사, 감시의 4가지 업무를 주기능으로 하면서 김해공항, 북부산, 양산, 창원, 마산, 경남 남부, 경남 북부의 7개 세관을 관할하고 있다. 1911년(또는 1910년) 건립된 청사 건물은 1979년 철거되고, 4층 탑 끝의 종탑만 현재 청사 뜰에 남아 있다.
부산해관은 인천, 원산해관과 함께 개항장에 설치된 대표적인 지방해관이다. 부산항이 근대 항만으로 자리잡는 데 중요한 기능을 하였다. 외국인 해관원을 통해 근대 외래문화를 수용하는 중요한 통로가 되었다.