1946년 6월 해방병단(海防兵團)이 통위부(統衛部) 산하의 부대로 승격된 것으로서 해안경비 임무를 수행하였다. 해방병단은 1945년 11월 광복 후 해사관계 단체인 조선해사협회의 건의에 따라 경상남도 진해(현재의 해군통제부)에서 70명의 인원으로 발족된 군사단체로 해안 및 도서순찰임무를 맡아왔다.
해방병단은 정식 군사조직이 아니었으므로 재정적 곤란이 컸으나 일본해군이 남기고 간 공작시설을 확보하여 조함창(造艦廠)을 세우고 폐선을 수리하여 취항시키는 등의 활약을 하면서 1,000명에 가까운 대원들을 확보하였다.
1946년 6월 15일 군정법령 제86호로서 통위부 산하 조선해안경비국이 조선해안경비대를 관할하게 되자 해방병단 총사령부는 1월 14일부로 조선해안경비대 총사령부로 소급하여 개칭하게 되었다.
그 해 9월 조선해안경비대는 미해군으로부터 상륙정 2척을 비롯한 몇 가지 함정을 인수받았으며 10월 사령부를 서울로 옮겼다. 1947년 진해·인천·목포·묵호·군산·포항·부산 등지에 기지를 설치하였고, 정부수립직전까지 병력 3,000명, 함정 105척을 확보하였으며, 정부가 수립되면서 해군으로 승격되었다.