After Pacificshakedown, Prime was reclassified MSO-466 on 7 February 1955. She completed major modification on 3 October 1955, and deployed to the Western Pacific on 1 May 1956. Following regular overhaul and type training in 1957, she deployed to WestPac again on 3 November 1958. In 1959 she enhanced her operational readiness through maneuvers with the South Korean Navy in January, and participation in an amphibious landing exercise off Kodiak, Alaska, in November.
Upon completion of overhaul and type training in 1960, she deployed to WestPac on 4 January 1961 and upon return began another overhaul on 20 November 1961. After training she deployed to WestPac again on 16 November 1962. She returned to Long Beach, California, in June 1963, and completed overhaul on 31 January 1964.
Vietnam War operations
Deployed to WestPac on 15 January 1965, she patrolled the coast of South Vietnam intermittently from May to August 1965, boarding approximately four suspect vessels per week to prevent enemy infiltration and supply. In 1966 she deployed to WestPac on 21 September, arriving off South Vietnam on 11 November, and patrolling the coast until 31 December.