Incredible was launched 21 November 1943 by Savannah Machine & Foundry Co., Savannah, Georgia; sponsored by Mrs. Herbert Hezlep; and commissioned 17 April 1944.
After shakedown along the U.S. East Coast and in the Caribbean, Incredible departed Norfolk, Virginia, 24 July, escorting a convoy to North Africa for the invasion of southern France, the Allies landing 15 August. She carried out her sweeping duties very effectively, sometimes without destroyer cover. On 10 September Incredible and her group repelled an attack of 12 human torpedoes, 2 of which she destroyed. She continued her minesweeping duties off southern France until 18 January 1945 when she sailed for a special mission to Russia and the Black Sea. Incredible performed sweeping duties out of Sevastopol, Russia, then served as an air-sea rescue patrol ship in the Black Sea until resuming to Palermo, Sicily, 20 February.
Incredible returned to Norfolk 5 May; and, after overhaul, departed 23 July for duty in the Pacific. She arrived Pearl Harbor eight days after the fighting stopped via the Panama Canal Zone and San Diego, California. The minesweeper sailed from Pearl Harbor 31 August for Operation Skagway, clearing the minefields in the East China Sea-Ryukyus area. This important duty lasted until 17 February 1946 when she returned to San Pedro, Los Angeles. She remained there until she decommissioned at Puget Sound 6 November, joining the Reserve Fleet. From 28 November 1947 to 28 September 1949 Incredible was "In Service, out of commission", based at Yokosuka, Japan.
Among her crew was Lee Van Cleef, who after the war became an actor known for his roles in Spaghetti Westerns.
Incredible was recommissioned 14 August 1950 at Yokosuka and departed 18 September for minesweeping and patrol duties in the Pusan area. While on patrol in mine-infested waters, on 12 October she rescued 27 survivors from USS Pirate (AM-275) which had struck a mine. Delivering her passengers to safety, she continued her operations in the battle zone, sweeping harbors and serving on patrol and escort duty. Returning to Yokosuka, Japan, Incredible sailed for Long Beach, California, arriving 4 August 1951.
The minesweeper operated along the U.S. West Coast and out of Pearl Harbor until 6 August 1953 when she sailed for the Far East. For the remainder of the year she operated out of Japan and on patrol along the coast of Korea
Incredible returned to Long Beach 11 March 1954 and was decommissioned there 21 September, again joining the Reserve Fleet. Reclassified MSF-249, 7 February 1955, Incredible remained in the Long Beach Group, Pacific Reserve Fleet until she was struck from the Navy List 1 December 1959. She was sold 8 August 1960 to National Metal and Steel Corp., Terminal Island, California.
Incredible received two battle stars for World War II service and four for Korean service.