MCCANDLESS' initial deployment was a six-month deployment as part of the Middle East Force in August 1973. April 1994 was spent as part of the Sea Control Force (TG 27.2) in company with USS MCDONNELL (DE-1043) and USS GUAM (LPH-9) in the Western Atlantic Operating Area. This task group was created to evaluate the Interim Sea Control Ship concept using the SH-3H helicopters and AV-8A Harrier jet aircraft embarked on GUAM. Following completion of the evaluation exercises, MCCANDLESS went on a two-month cruise to the North Atlantic to participate in the NATO exercise "Northern Merger" returning to her homeport of Norfolk, Virginia in November 1974. In April 1975 MCCANDLESS joined the Sixth Fleet for the first of two six-month deployments. Upon completion of her second deployment in the fall of 1976, MCCANDLESS returned to Norfolk for installation of the prototype Integrated Bridge System (IBS), a fully automated maneuvering and navigational system. The following eight months were spent testing and evaluating the IBS prototype system in the western Atlantic including participation in a joint Canadian-US exercise, MARCOTCANUS 77.

In September 1977, MCCANDLESS changed homeports to Philadelphia to commence her first major overhaul since commissioning. The overhaul at Philadelphia Naval Shipyard spanned ten months ending in June 1978 and included removal of the IBS and the addition the Harpoon weapon system and the 'rubber window' to the sonar dome. Following two months of refresher training at Guantanamo Bay, Cuba, MCCANDLESS returned to her homeport of Norfolk and rejoined the Second Fleet. MCCANDLESS participated in fleet exercise COMPTUEX 2-79 and then returned to the Caribbean off St. Croix, U.S. Virgin Islands, in April 1979 to conduct technical and operational evaluation of the first production model of the AN/SLQ-32(V1) electronic warfare suite. She deployed to the Sixth Fleet in June 1979 for six months of operations in the Mediterranean. Following an initial port visit to Alghero, Sardinia, MCCANDLESS participated in fleet exercises in the eastern Mediterranean and a port visit to Haifa, Israel hosted by the Israeli Navy and in company with USS INDEPENDENCE (CV-62). MCCANDLESS participated in the exercise DISPLAY DETERMINATION 79 in the Aegean Sea and was commended for being the best Naval Gunfire Support (NGFS) ship supporting the landing force. Following a brief visit to Athens, Greece, she passed through the Suez Canal in August to begin a two-month deployment augmenting the Middle East Force. This deployment included conducting operations while on patrol in the Red Sea and Gulf of Aden with brief stops in Djibouti. Returning through the Suez Canal to the Mediterranean to rejoin the task group in early October, MCCANDLESS was then tasked with special operations in the Black Sea and passed through the Bosporus and Dardanelles in company with USS CARON (DD-970) later that month for this operation. Completion of the Black Sea operations allowed a port visit to Istanbul, Turkey. The remaining deployment included various NATO and fleet exercises and port visits to Genoa, Italy, Toulon, France, and Palma, Spain. While supporting a bilateral fleet exercise with the French south of the Balearic Islands, the task group was beset by a mistral (severe storm) and MCCANDLESS, responding to a distress call, saved three French citizens from their sinking yacht "Le Crok" which had foundered in the high seas. MCCANDLESS returned to Norfolk in December 1979.