The Nahoke was laid down by the Consolidated Shipbuilding Corp., Morris Heights, New York. She was assigned to the 15th Naval District, operated in the Panama Canal Zone until transferred to the 5th Naval District. She was headquartered at Norfolk, in the spring of 1961. In February 1962, the Nahoke was redesignated YTM–536, and continued, into 1970, to provide vital tug services to naval vessels and commands in the Chesapeake Bay area.