The contract for Neodesha was awarded on 22 June 1970. She was laid down on 10 May 1971 at Sturgeon Bay, Wisconsin, by Peterson Builders and launched 6 October 1971.
Neodesha served the 14th Naval District at Pearl Harbor, Hawaii.
On 3 August 2007 she was reclassified as an unclassified miscellaneous vessel, given the hull number IX-540. Neodesha is assigned to Mobile Diving and Salvage Unit One as a non-operational training hulk. Neodesha was stricken from the naval register on 28 May 2021.