국가경제수준의 세계화와 해양환경보전 및 해양자원보전이 절실하게 요구되어 해양수산업무의 확대 · 강화의 요청으로 인해 1996년 8월에 이전의 농림수산부 산하의 수산업무와 건설교통부 산하의 해운항만업무, 내무부 산하의 해양경찰업무, 환경부 산하의 해양환경업무을 통합하여 발족하였다.
장 · 차관아래 차장보 2인이 있으며, 그 아래 해양수산부의 정책과 기획을 조정하고 이를 심사 · 분석하며, 예산 · 행정관리 · 법제 · 투자심사 및 전산통계의 사무를 관장하는 기획관리실이 있다.
하부조직으로 총무과 · 공보관 · 감사관 · 비상계획관 등 일반조직 외에 국제협력관 · 해양정책실 · 해운선박국 · 항무국 · 항만건설국 · 수산진흥국 · 수산자원국 · 수산물유통국이 있다.
국제협력관은 국제연합해양법협약 등 해양 · 심해저 광물관련 · 어업협정 · 해외정보자료 · 해양과학기술 · 해운 · 항만 · 수산 · 해양환경 · 수로표지 및 해상안전 등 분야의 국제협력 및 국제기구 · 원양어업 등에 관한 사무를 수행한다.
해양정책실은 해양수산과 해양개발에 관한 기본계획, 중 · 장기종합계획의 수립 및 해양개발, 투자사업계획의 종합 · 조정 등과 해양자원의 조사 · 연구 및 관련 기술개발, 심해저 광물자원의 개발, 해양에너지의 조사 · 연구, 해양과학교육의 진흥 등에 관한 사무를 수행한다.
또한 해양환경보전계획을 수립하여 이를 시행하고 해양오염원을 조사 · 규제하며, 해양안전 · 종합계획을 수립하여 해난 · 오염사고 수습을 종합지휘하고 국제안전관리규약 및 사업장 지도 · 감독에 관한 사항 등을 관장한다.
해운선박국은 해운정책 · 외내항 · 선박기술 · 선박검사 · 어선 · 표지 등에 관한 업무를 수행한다. 항무국은 항만에 관한 각종 정책을 수립하고, 항만을 운영하며, 항만 내 물류의 유통과 선원 · 노정에 관한 사무를 수행한다.
항만건설국은 항만건설을 기획하여 이를 시행하고 공업단지안의 산업항을 관리하며 시설안전 · 개발 및 신항만기술에 관한 사무를 담당한다.
수산진흥국은 수산관련정책을 종합 · 조정하고 어촌개발종합계획을 수립하여 생활환경을 개선하며 어업인 후계자 · 전업 어업인 · 선도 어업인을 교육 · 육성하는 등 어업인 복지와 각급 어항에 관한 일을 수행한다.
수산자원국은 수산물생산에 관한 종합계획을 수립하고 연근해 어업 · 어업지도 · 양식 · 자원조성 · 어장보전 등에 관한 사무를 한다.
수산물유통국은 수산물의 유통과 수급에 관한 종합계획을 수립하여 이를 시행하고 각종 유통구조를 개선하며 수산물 가공에 관한 종합계획을 수립하여 가공산업을 육성 · 발전시키고 수산물수출입정책을 수립하여 수출입을 진흥시키는 사무를 관장한다.
이 밖에 해양수산부장관 소속하에 국립수산과학원, 국립해양조사원, 국립수산물품질관리원, 해양수산인재개발원, 동해어업관리단, 서해어업관리단, 항로표지기지창을 두고 있다.
지방에서 장관의 관장사무를 분장하는 지방 해양수산청과 어항사무소 및 해난사건을 심판하는 해양안전심판원(海洋安全審判院)이 있다.