Đầu năm 1960, cùng với phong trào Đồng khởi Bến Tre, phong trào cách mạng của các tỉnh đồng bằng Nam Bộ chuyển mạnh lên thế tiến công và trở thành cao trào đồng khởi rộng khắp. Để đáp ứng yêu cầu vận chuyển vũ khí, hàng hóa chi viện cho chiến trường Nam Bộ và Nam Trung Bộ, trong khi vận chuyển đường bộ của Đoàn 559 chưa vươn tới; Tổng Quân ủy chỉ đạo Bộ Tổng Tham mưu khẩn trương nghiên cứu đề án mới về xây dựng và tổ chức lực lượng vận tải biển chi viện cho chiến trường Nam Bộ và Khu 5.
Trong khi chưa có lực lượng để làm nhiệm vụ vận chuyển trên biển chi viện cho miền Nam, Bộ Chính trị chỉ thị cho Trung ương Cục miền Nam chỉ đạo các tỉnh ven biển ở miền Trung và Nam Bộ chủ động chuẩn bị bến, bãi và tổ chức đưa thuyền vượt biển ra miền Bắc, vừa thăm dò, nắm tình hình địch, nghiên cứu tuyến vận chuyển trên biển, vừa nhận vũ khí để cung cấp cho cách mạng ở miền Nam.
Vào 22 giờ 10 phút ngày 11/10/1962, chuyến tàu đầu tiên chở vũ khí đã xuất phát từ bến K15, Đồ Sơn, Hải Phòng đi Cà Mau. Chuyến tàu cập bến thành công, đánh dấu cho việc mở đường thắng lợi. Cán bộ, chiến sĩ Đoàn tàu Không số đã vô cùng anh dũng hoàn thành xuất sắc nhiệm vụ trên biển, khai thông tuyến đường vận chuyển chiến lược - một con đường có một không hai trên thế giới. Sau đó, từ năm 1961 đến 1962 đã có 5 thuyền của địa bàn Nam Bộ (tỉnh Bạc Liêu, Trà Vinh, Bến Tre, Bà Rịa) đã ra tới miền Bắc. Những chuyến thuyền từ Nam Bộ vượt biển ra Bắc thành công là một trong những cơ sở quan trọng để xúc tiến việc thành lập đoàn vận tải thủy tiếp tế vũ khí cho miền Nam.
Ngày 23/10/1961, Bộ Quốc phòng ban hành Quyết định số 97/QP về việc thành lập Đoàn 759 vận tải thủy. Ngày 23/10 trở thành ngày truyền thống của đoàn 759 trước đây, Lữ đoàn 125 Hải quân ngày nay, đồng thời là Ngày mở Đường Hồ Chí Minh trên biển. Chỉ trong vòng 1 năm đầu tiên, Đoàn 759 đã thực hiện 29 chuyến hàng vào Nam Bộ, vận chuyển 1.430 tấn vũ khí cho chiến trường.
Đến ngày 29/1/1964, Bộ Quốc phòng quyết định đổi phiên hiệu Đoàn 759 thành Đoàn 125. Trong vòng 14 năm, từ năm 1961 đến năm 1975, gần 2.000 lượt chiếc tàu không số, vượt qua hơn 20 cơn bão lớn, hàng trăm cuộc vây ráp của kẻ thù, đi gần 4 triệu hải lí, vận chuyển 15 vạn tấn vũ khí trang bị và 8 vạn lượt người, góp phần chi viện đắc lực cho chiến trường, cùng toàn dân, toàn quân đưa cuộc kháng chiến chống Mỹ, cứu nước đến thắng lợi hoàn toàn. Bên cạnh đó, Đoàn 125 cũng đã trực tiếp chiến đấu với 30 lần tàu chiến, 1.200 lượt máy bay địch, khắc phục rà phá 4.000 quả thủy lôi, bắn rơi 5 máy bay, bắn chìm và bắn hỏng 5 tàu chiến, bắt 42 tù binh…
Trong cuộc Tổng tiến công và nổi dậy mùa Xuân 1975, các đội tàu của Đoàn 125 tiếp tục vận chuyển hàng hóa, lực lượng phục vụ cho việc giải phóng các tỉnh và các đảo ven biển miền Nam, chi viện cho các lực lượng làm nhiệm vụ giải phóng quần đảo Trường Sa. Thực hiện mệnh lệnh “thần tốc” của Đại tướng Võ Nguyên Giáp, phải vận chuyển thật nhanh những vũ khí hạng nặng và hàng chục ngàn cán bộ, chiến sĩ vào miền Nam, kịp thời hiệp đồng tác chiến với cánh quân đường bộ.
Đặc biệt, ngày 4/4/1975, Quân uỷ Trung ương đã chỉ thị cho Khu uỷ, Bộ Tư lệnh Quân khu 5 và Bộ Tư lệnh Hải quân phải nghiên cứu và chỉ đạo thực hiện gấp rút, nhằm thời cơ thuận lợi nhất đánh chiếm các đảo do quân nguỵ Sài Gòn chiếm thuộc quần đảo Trường Sa. Sau đó, do tình hình chiến sự miền Nam phát triển rất nhanh, Bộ Tổng tham mưu đã ra lệnh cho Bộ Tư lệnh Hải quân nhanh chóng giải phóng Trường Sa. Chính vì quyết định nhanh chóng và đúng đắn này, từ ngày 14 đến 29/4/1975, các lực lượng của ta đã nhanh chóng giải phóng và tiếp quản các đảo Song Tử Tây, Sơn Ca, Nam Yết, Sinh Tồn và Trường Sa. Tiếp đó Đoàn 125 tham gia giải phóng một số đảo ở miền Trung và vùng biển Tây Nam.
Với những thành tích đã đạt được, Đoàn 125 vinh dự được Đảng, Nhà nước hai lần tuyên dương Đơn vị Anh hùng Lực lượng vũ trang Nhân dân, 6 Huân chương Quân công, 12 Huân chương Chiến công; cùng 13 tập thể và 22 cá nhân được tuyên dương Anh hùng Lực lượng vũ trang Nhân dân… Đặc biệt, Tàu HQ - 671 được Thủ tướng Chính phủ công nhận Bảo vật quốc gia.
Tiếp nối tinh thần yêu nước của cha ông, Hải quân, Cảnh sát biển, Bộ đội Biên phòng, Kiểm ngư đã phối hợp hoạt động, trở thành lực lượng nòng cốt trong nhiệm vụ bảo vệ chủ quyền, an ninh biển, đảo của Tổ quốc. Bên cạnh đó, mỗi tàu cá của ngư dân Việt Nam cũng đã thực sự trở thành một cột mốc sống, mỗi ngư dân Việt Nam đã đóng góp to lớn vào việc bảo vệ chủ quyền biển, đảo. Thủ tướng Chính phủ cũng đã ban hành Chỉ thị 01 về việc tổ chức phong trào toàn dân tham gia bảo vệ chủ quyền lãnh thổ, an ninh biên giới quốc gia trong tình hình mới (9/1/2015).
Thế kỉ XXI được coi là “Thế kỉ của đại dương”. Bởi vậy, nước ta phải trở thành quốc gia mạnh về biển, làm giàu từ biển. Do đó, 3.260km bờ biển, 1 triệu km2 vùng biển thềm lục địa, trên 3.000 hòn đảo lớn, nhỏ và hai quần đảo Hoàng Sa, Trường Sa là địa bàn chiến lược về kinh tế, quốc phòng, an ninh, đối ngoại và môi trường sinh thái có vị trí đặc biệt quan trọng trong sự nghiệp xây dựng, phát triển và bảo vệ Tổ quốc Việt Nam.
Nghị quyết số 36-NQ/TW, ngày 22/10/2018 của Hội nghị lần thứ 8 Ban Chấp hành Trung ương Đảng (khóa XII) về Chiến lược phát triển bền vững kinh tế biển Việt Nam đến năm 2030, tầm nhìn đến năm 2045 xác định: “Việt Nam phải trở thành quốc gia mạnh về biển, giàu từ biển, phát triển bền vững, thịnh vượng, an ninh và an toàn; phát triển bền vững kinh tế biển gắn liền với bảo đảm quốc phòng, an ninh, giữ vững độc lập, chủ quyền, toàn vẹn lãnh thổ”. Biến mục tiêu đó thành hiện thực là cách tốt nhất để kế thừa, gìn giữ, phát huy và bảo vệ các vùng biển đảo thiêng liêng của cha ông cho con cháu mãi mãi mai sau.
