The contract for Natchitoches was awarded 2 May 1968. She was laid down on 24 June 1968 at Slidell, Louisiana, by Southern Shipbuilding Corp and launched 9 January 1969.
Placed in service 29 May 1969, Natchitoches assigned to Boston. She served in Boston, Naval Station Puget Sound, Everett, Washington, and 6th Naval District at Charleston, South Carolina until her retirement in 1995.
Stricken from the Navy List 13 October 1995, she was transferred to the United States Army Corps of Engineers 28 December 1995. Ex-Natchitoches was renamed D. L. Billmaier.