From 24 April 1965, "Joseph Strauss", together with , was part of the first advanced search and rescue/anti-air warfare (SAR/AAW) picket team in the Gulf of Tonkin to support U.S. air strike operations against North Vietnam. From 16 through 21 May, she observed operations of a Russian task unit. She returned to Yokosuka from 23 May to 4 June, then again sailed for the Gulf of Tonkin. Her ensuing 27 days as flagship of the SAR/AAW picket unit were highly successful, establishing operational procedures and capabilities which remain destroyer standards. On 17 June 1965, two F4B Phantoms from , under "Joseph Strauss" advisory control, shot down two MiG-17s, accounting for the first two hostile aircraft downed by U.S. forces in aerial combat since 1953. Three days later, two propeller-driven Skyraiders, also from "Midway" and under "Joseph Strauss" advisory air control shot down another MiG-17. As a result, members of "Strauss" Combat Information Center team were decorated by the Secretary of the Navy.