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