The contract for Okmulgee was awarded 7 December 1961. She was laid down on 3 July 1962 at Slidell, Louisiana, by Southern Shipbuilding Corporation and launched 18 April 1963.
Okmulgee reported for duty in the 5th Naval District, headquartered at Naval Station Norfolk, Virginia, in April 1963. Prior to 2005, Okmulgee was assigned to the Kings Bay Naval Submarine Base. Stricken from the Navy Directory 25 May 2005, she was taken out of service and sold by the Defense Reutilization and Marketing Service (DRMS) to McAllister Towing of Virginia for $136,000, renamed Steven McAllister.[2]