Ngày 17/3/1963, chiếc tàu vỏ sắt đầu tiên do đồng chí Đinh Đạt làm thuyền trưởng, đồng chí Nguyễn Văn Tiến làm chính trị viên chở 44 tấn vũ khí lên đường đến bến Trà Vinh an toàn. Nhờ tổ chức tốt, kỷ luật nghiêm, ý thức trách nhiệm cao, tinh thần vững vàng và trình độ chuyên môn giỏi, những chuyến đi của Đoàn đều hoàn thành tốt nhiệm vụ và giữ được bí mật.
Từ dấu mốc lịch sử đó đến năm 1975, với tinh thần và quyết tâm Táo bạo - bí mật - bất ngờ, vượt qua thử thách ác liệt, khắc phục khó khăn để vận chuyển chi viện cho chiến trường góp phần đánh thắng chiến lược “Chiến tranh đặc biệt”, “Chiến tranh cục bộ” và “Việt Nam hóa chiến tranh” của đế quốc, góp phần giải phóng hoàn toàn miền Nam, thống nhất đất nước. Sau ngày đất nước thống nhất, Bộ Quốc phòng quyết định[2] “Về tổ chức lực lượng Lữ đoàn 172”, trong đó Đoàn 125 đổi tên thành Hải đoàn 125 và sáp nhập vào Lữ đoàn 172. Năm 1976, lần đầu tiên chiến dịch vận chuyển cho quần đảo Trường Sa được thực hiện. Hải đoàn 125 đã huy động 11 lượt tàu, đi 22 chuyến, chở 2.300 tấn hàng ra đảo và làm nhiệm vụ cắm mốc chủ quyền, chở các tù chính trị từ đảo Phú Quốc về đất liền an toàn.
Đường Hồ Chí Minh trên biển là một thiên anh hùng ca bất tử, một bộ phận quan trọng của hệ thống vận tải quân sự chiến lược trong cuộc kháng chiến chống xâm lược, giải phóng đất nước, xây dựng nên truyền thống vẻ vang. Một là, trung thành vô hạn với Đảng, với Tổ quốc, với chế độ xã hội chủ nghĩa và nhân dân; nêu cao ý chí quật cường, dũng cảm; khát vọng độc lập, tự do và niềm tin vào thắng lợi cuối cùng; sẵn sàng xả thân chiến đấu hy sinh để hoàn thành xuất sắc mọi nhiệm vụ được giao. Hai là, phát huy sức mạnh tổng hợp, chỉ huy tập trung thống nhất, hiệp đồng chặt chẽ với các lực lượng, chính quyền và Nhân dân các địa phương, sự giúp đỡ của bạn bè quốc tế để hoàn thành xuất sắc mọi nhiệm vụ được giao. Ba là, nêu cao ý thức độc lập, tự chủ, tự lực, tự cường; đoàn kết, thống nhất, kỷ luật nghiêm minh; nắm vững khoa học kỹ thuật; khắc phục khó khăn, phá thế bao vây của địch; linh hoạt, mưu trí, sáng tạo, liên tục tiến công, quyết chiến, quyết thắng; tìm ra nhiều phương thức vận chuyển có hiệu quả.
Với những thành tích xuất sắc đã đạt được, Đoàn 759 đã được tặng thưởng Huân chương Chiến công hạng Hai; Tàu 41 được tặng Huân chương Quân công hạng Nhất; các tàu 43, 54, 55 và 56 được tặng Huân chương Chiến công hạng Nhất; các tàu 42, 67 và 68 được tặng Huân chương Chiến công hạng Nhì. Đoàn 125 được tặng thưởng Huân chương Quân công hạng Nhất, hai lần được tặng danh hiệu Anh hùng Lực lượng vũ trang nhân dân[3]. Tổng kết đợt hoạt động “Chiến dịch CQ-88” (năm 1988), Lữ đoàn 125 có 2 tập thể: Tàu HQ505, tàu HQ931 và 1 cá nhân được tuyên dương danh hiệu Anh hùng Lực lượng vũ trang nhân dân. Lữ đoàn 125 được tặng thưởng Huân chương Quân công hạng Nhất (năm 2011), Huân chương Bảo vệ Tổ quốc hạng Nhì (năm 2016).
Phát huy truyền thống Đường Hồ Chí Minh trên biển, cán bộ, chiến sĩ lực lượng Hải Quân nói riêng, toàn quân nói chung nêu cao ý thức độc lập, tự chủ, tự lực, tự cường; chủ động, sáng tạo, cần kiệm lao động sản xuất, làm chủ vũ khí, trang bị kỹ thuật chiến đấu và chiến thắng bảo vệ vững chắc Tổ quốc thân yêu của chúng ta. Trí Ánh
[1] Lực lượng của Đoàn ban đầu có 38 cán bộ, chiến sĩ, trong đó có 20 đồng chí thuộc các thuyền của Bến Tre, Trà Vinh và Liên khu V vừa điều ra.
[2] Quyết định số 142-QĐ/QP, ngày 26/10/1975
[3] Lần thứ nhất ngày 01/01/1967 và lần thứ hai ngày 03/6/1976.