Named for the Patoka River, Patoka was laid down on 17 December 1918 by the Newport News Shipbuilding and Dry Dock Company of Newport News, Virginia and launched on 26 July 1919. Acquired by the Navy from the United States Shipping Board on 3 September 1919, and commissioned on 13 October 1919.
Assigned to the Naval Overseas Transportation Service, Patoka departed Norfolk on 4 November 1919 for Port Arthur, Texas, where she loaded fuel oil and sailed for Scotland, arriving on the Clyde on 6 December. She returned to Port Arthur for more oil and got under way on 9 January 1920 for the Adriatic Sea, arriving at Split on 12 February. Returning to the United States in April Patoka went back to the Near East, arriving at Istanbul in June. After duty in the Adriatic and Mediterranean she returned to the United States, and served on both the east and west coasts until 1924 when she was selected as a tender for the rigid airship .
A mooring mast some 125 feet above the water was constructed; additional accommodations both for the crew of Shenandoah and for the men who handled and supplied the airship were added; facilities for the helium, gasoline, and other supplies necessary for Shenandoah were built; as well as handling and stowage facilities for three seaplanes. This work by the Norfolk Navy Yard was completed shortly after 1 July 1924. Patoka retained her classification of AO–9.
Patoka engaged in a short series of mooring experiments with the Shenandoah, which had reported to the Commander, Scouting Fleet, for duty on 1 August 1924. The first successful mooring was made on 8 August 1924.
In October, Patoka, along with the cruisers and, were assigned stations in the mid-Atlantic to furnish the US Navy's second operational airship,, with the weather reports and forecasts during her flight, 12 to 15 October 1924, from Germany, where she had been built, to Lakehurst Naval Air Station, New Jersey.
During 1925 Patoka operated with both Shenandoah and Los Angeles in demonstrating the mobility of airships, and in reducing the number of ground personnel required to handle them. A projected polar flight by Shenandoah, using Patoka as her base of operations, was cancelled when the airship was lost in a storm on 3 September 1925.
Between 1925 and 1932 Patoka operated with Los Angeles and served as her base of supply and operations on her long-range flights to Puerto Rico (1925), Panama (1928), Florida (1929), and during the fleet concentration off Panama (1931). During 1932 she also operated with the newly acquired airship, but the decommissioning of Los Angeles on 30 June 1932, and the loss of Akron on 4 April 1933 saw a reduced need for an airship tender, with Patoka decommissioned on 31 August 1933.
On 10 November 1939 Patoka recommissioned at the Puget Sound Navy Yard, Comdr. C.A.F. Sprague in command, and reported to Patrol Wing 5, Aircraft, Scouting Force. Her classification had been changed to AV–6, seaplane tender, on 11 October 1939.
On 18 January 1940 she departed Puget Sound and, after taking on fuel and cargo at San Pedro, arrived at San Diego on the 31st. She steamed for the east coast on 5 February and reached Norfolk on 25 March. Next Patoka was assigned to the Naval Transportation Service in June and was reclassified AO–9 on 19 June 1940.
On 13 August she departed Norfolk and sailed to Houston. Between August and December 1940, she operated out of Houston and Baytown, Texas, delivering fuel oil to Boston, Melville, Norfolk, Charleston, and Key West.
From March 1941 to September Patoka delivered fuel oil and general cargo to various units of the Fleet in the Atlantic, Gulf, and Caribbean areas. On 28 September she departed Norfolk and proceeded, via Aruba, to Recife, Brazil. Patoka made one more round trip to Recife before the United States entered World War II.
On 7 December 1941, Patoka was moored at Recife, acting as tanker, cargo, store ship, and repair ship. Here she supplied the units of Task Force 3 (later 23) with fuel, diesel, lubricating oil; gasoline stores; provisions; and repairs.
Shortly after the turn of the new year 1942, she got under way for Bahia, Brazil, anchoring there on 8 January. There, she received word that ships bearing rubber and other vital war goods had left French Indochina bound for the Axis controlled ports in Europe. Patoka requested and received permission to patrol the shipping lanes off Bahia. When she had completed her patrol duties she put into port and returned to Recife on 22 January. Six days later she was bound for San Juan, Puerto Rico, but en route she was diverted to Trinidad, BWI. Taking on fuel and stores she returned to Recife. Standing out of the harbor on 21 February, she again set course, changed several times to avoid reported submarines, and reached San Juan, Puerto Rico, on 4 March. Her return trip to Recife was made without incident.
On 25 May 1942, while again returning to Recife from Trinidad escorted by, Patoka sighted an enemy submarine on the surface. Jouett attacked, forcing the U-boat to dive and continued the attack until Patoka had escaped. Patoka remained at Recife, continuing to supply the ships of Task Force 23 with provisions, supplies and tender services until April 1943, with occasional trips to Puerto Rico and Trinidad for replenishment. Patoka then got underway for home, reaching Norfolk on 22 May for overhaul. She sailed for New York on 6 August to join a convoy bound for Aruba, N.W.I. and resumed operations along the coast of South America.
In April 1944, she carried 62 prisoners of war (German naval and merchant marine personnel) from Rio de Janeiro to Recife where they were turned over to the U.S. Army. Patoka departed on 24 March and arrived Norfolk on 6 April for an overhaul period, to prepare for duty in the Pacific.
On 15 June, Patoka departed from Norfolk for the Panama Canal and Pearl Harbor. There she was outfitted for duty as a minecraft tender and was reclassified AG–125 on 15 August 1945. Shortly thereafter she sailed via Guam for Okinawa, reaching Buckner Bay on 5 September. Patoka provided the minecraft with tender services until 21 September at which time she got underway for Wakayama, Japan. Anchoring there on 23 September, she continued to provide logistic support to units of the 5th Fleet, servicing mine vessels of Task Group 52.6. She remained with the occupation forces until the spring of 1946, returning to the United States on 10 March 1946.
Patoka was decommissioned on 1 July 1946, transferred to the War Shipping Administration, and was struck from the Navy List on 31 July 1946. She was sold to Dulien Steel Products Co. for scrap on 15 March 1948.