With her ASW readiness at its highest and under the command of her new CO, Commander John C. Hill II, she set sail on her first Mediterranean deployment to join the 6th Fleet on 7 August 1959. Underway in accordance with CT 24.4.2 movement 4-59, she joined up with the task unit at 1017. She crossed the Atlantic with DESRON 32 minus USS Strong and USS Lowry. Joining her were USS Nantahala AO-60, USS Canisteo AO-99, USS Suribachi AE-21, USS Hale DD-642, USS Benham DD-796, USS Fiske DDR-842, and USS Hawkins DDR-873. This task force rendezvous with USS Essex CVA-9 on 12 August.
On 18 August, she proceeded to anchorage Alpha Two Golfo de Palmas, Sardinia. Golfo de Palmas is in the south-west portion of Sardinia. The island of S. Antioco, joined by a narrow isthmus and a group of bridges to the mainland, forms a good natural harbor to the south of the isthmus. Other ships present included USS Boston CAG-1 (ComCruDiv 2 embarked), USS F. D. Roosevelt CVA-42 (ComCarDiv 2 embarked), sister ship USS Bigelow DD-942 (COMDESRON 6 embarked), USS J. C. Owens DD-776 (COMDESDIV 322 embarked), USS Zellars DD-777 (COMDESDIV 162 embarked), USS Charles S. Sperry DD-697, USS Massey DD-778, USS Meredith DD-890, along with USS Lowry and USS Fox.
Upon arriving in the Mediterranean, Mullinnix (and Bigelow) were the newest United States destroyer in the Mediterranean, in addition to being the flagship for Commander, Destroyer Squadron (DESRON) 32. As such, she was visited by many dignitaries including West German Minister Strauss. Minister Strauss had the opportunity to experience highline transfers close up and personal as he arrived from the heavy cruiser USS Des Moines CA-134 at 1355 on 22 August. He departed Mullinnix the same way he arrived, highlining to the USS Roosevelt.
On a picturesque morning sunrise came early at 0543. The crew, hypnotized by a beam of morning sunlight coming through the portholes, was called to set the special sea detail at 0710. They had several days of hard work in front of them before they would experience liberty. Days were filled with tactical drills with other ships, refueling, ECM exercises, man overbroad drills, general quarters that included firing of all 5-inch mounts using VTNF projectiles. Nights were filled with additional NATO exercises and major fleet operations. She took on stores from USS Alstede AF-48 and USS Altair AKS-32, refueled from USS Nantahala on 23 August.
The nuclear powered submarine USS Skipjack SSN-585 commenced making runs between Mullinnix and USS Des Moines to demonstrate her nuclear powered capabilities. This was followed by ASW attack team exercises, the first for the crew that involved a nuclear submarine.
On 24 August, Mullinnix steamed into Marseilles, France for much deserved liberty.