Choctaw was laid down 4 April 1942 by Charleston Shipbuilding and Drydock Co., Charleston, South Carolina and launched on 18 October 1942. She was commissioned 21 April 1943.[1]
From 17 June 1943 to 8 May 1944, Choctaw served at Bermuda, where she aided assembling convoys and new ships undergoing training with tug and target-towing services. Putting to sea 8 May, she was reclassified ATF-70, 15 May, and reached Oran 19 May to take USS Holder (DE-401) in tow for New York City, where she delivered her tow 9 June. She returned to her duties at Bermuda until 22 July, when she sailed for ports in Wales to take two LSTs in tow for New York, arriving 30 September.
After overhaul at Norfolk, Virginia, Choctaw sailed for tug duty at St. John's and Argentia, Newfoundland, between 20 November 1944 and 8 December, when she sailed to rendezvous with . She took the collision-damaged ship in tow for Bermuda and Charleston, and returned to Newfoundland for service between 3 January 1945 and 14 March. She then operated off the east coast and in the Caribbean on salvage duty and in towing targets until 15 October 1946. Afterwards, she sailed to Orange, Texas to be placed out of commission, and in reserve, on 11 March 1947. She would remain there for three decades.
After being laid up in the Atlantic Reserve Fleet for 30 years, she was struck from the Naval Register on 31 October 1977, and transferred to the Colombian Navy under the Security Assistance Program on 1 March 1978 as ARC Pedro De Heredia (RM-72).