Following shakedown and a brief tour on the east coast, Navajo, an oceangoing fleet tug, steamed to San Diego, where, in June 1940, she reported for duty in Base Force, later Service Force, Pacific Fleet. Until the Japanese attack on Pearl Harbor, the ship's towing and salvage capabilities were utilized in the central and eastern Pacific, and then, after 7 December 1941, in the Pearl Harbor area. 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. Navajo then returned to Pearl Harbor, where she got underway for the war zone on 12 July 1942. Arriving in the New Hebrides just after the landings on Guadalcanal, she supported operations in the Solomons with repair and salvage work at Espiritu Santo, Nouméa, Tongatapu, and Suva, as well as under battle conditions at Tulagi, Guadalcanal, and Rennell.^[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. Navajo took off 440 survivors which were transferred to the cruiser USS Chester.^[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.^[1]

On January 30, 1943, Navajo attempted to tow the badly damaged heavy cruiser USS Chicago away from the combat zone during the Battle of Rennell Island, but was unsuccessful as Chicago was finished off by a squadron of Japanese torpedo bombers. She then towed to safety the destroyer USS La Vallette, who had suffered a torpedo hit during the battle.

In the spring of 1943, Navajo returned to California, underwent overhaul, and in July 1943 got underway to return to the South Pacific. Steaming via Pago Pago, she arrived at Bora Bora on 21 August 1943 and commenced salvage and repair work on USS Pasig. At the end of the month, the ship sailed for Pago Pago, whence she got underway to tow gasoline barge YOG–42 to Espiritu Santo.^[1]

While en route to Espiritu Santo on 12 September 1943, the ship was torpedoed by Type B1 submarine I-39 and rocked by an explosion. Within seconds, a heavy starboard list resulted in a submerged starboard side. Navajo began going down rapidly by the bow and the order was given to abandon ship. As the ship settled, depth charges secured to port and starboard K-gun projectors exploded. An estimated two minutes had passed before the tug sank. 17 members of her crew died during the attack.^[1]

• American Defense Service Medal
• American Campaign Medal
• Asiatic-Pacific Campaign Medal with two battle stars (NavSource notes the tug was awarded a battle star for her salvage operations between 8 August 1942 and 3 February 1943.)^{[3][note 1]}
• World War II Victory Medal

• This article incorporates text from the public domain Dictionary of American Naval Fighting Ships.

• Ships of the U.S. Navy, 1940–1945 ATF-64 USS Navajo
• USS Navajo (AT 64) at uboat.net
• Navajo class at uboat.net
• Vessels/Auxiliaries: USS Navajo from the United States Naval Institute Archived 2007-09-28 at the Wayback Machine
• "7 December 1941" – Ships in Pearl Harbor Archived 10 August 2020 at the Wayback Machine

14°58′35″S 169°17′57″E / 14.97639°S 169.29917°E / -14.97639; 169.29917