[1] Navajo was laid down by the Bethlehem Shipbuilding Corporation, Staten Island, New York, on 12 December 1938; launched on 17 August 1939, sponsored by Miss Olive Rasmussen; and commissioned on 26 January 1940.

Interrupted only by a resupply and reinforcement run to Johnston Island at the end of December 1941, she remained in the waters off Oahu into the spring of 1942.

[1] In late April 1942, Navajo sailed to Canton Island where she and other vessels attempted the unsuccessful salvage of the 502 ft. troop ship SS President Taylor, who had been grounded on a coral reef.

[1] In October the tug assisted with rescue of survivors aboard the troop transport President Coolidge after she struck mines in the entrance to the harbor at Espíritu Santo.

[2] Towing assignments during those operations took the vessel throughout the island groups of the South Pacific, and once in late November-early December, 1942 to Sydney, Australia.