The roots of this service may be traced to the May 5, 1976 Resolution "On the Protection of artificial structures on the Trans-Baikal and Far Eastern Railways" of the Politburo of the Communist Party of the Soviet Union.

As a result, problems have been identified for both the Baikal-Amur Mainline and the Trans-Siberian Railway, providing the basis for the 1978 formation of the first units of boats and naval divers of what was then the Naval Service of the Internal Troops of the Ministry of Internal Affairs of the Union of Soviet Socialist Republics or NS-IT-MIA-USSR (Морские части внутренних войск МВД CCCP, Morskiye Chasti Vnutrennikh Voysk MVD SSSR) with the approval of the suggested measures and subsequent decrees of the Council of Ministers.

In 1984, through a general order of the chief of internal troops of the parts on the protection of sea lanes, two patrol boat divisions were raised.

Through a Decree of the USSR Council of Ministers on May 18, 1989 "On the Repair and technological enterprise of the nuclear fleet" (which gave military protection to personnel from today's FSUE Atomflot and the Murmansk Shipping Company) and a Decree of the Council on August 3 the same year the organizational and staffing structure was approved for the 2 naval patrol boat divisions assigned in Murmansk to the Naval Service of the MVD.

On the basis of part of personnel of the 1st Naval Detachment (Khabarovsk), the 5th Independent Maritime Training Division (Severobaikalsk) was raised on October 1, 1996.