| 6. June 1960 CVSG-58 established |
| CVS-15 USS Randolph | ||
| February 1960 - March 1960 | ||
| North Atlantic | ||
| VS-36 | S2F-2 | AV 30 |
| VAW-12 Det. | AD-5W | GE 00 |
| HS-7 | HSS-1 | AV 50 |
| CVS-15 USS Randolph | ||
| April 1961 - May 1961 | ||
| Caribbean | ||
| VS-26 | S2F-2 | AV 00 |
| VS-36 | S2F-2 | AV 30 |
| VAW-12 Det. 36 | AD-5W | GE 00 |
| HS-7 | HSS-1N | AV 50 |
| HU-2 Det. 36 | HUP-3 | HU 00 |
| CVS-15 USS Randolph | ||
| July 1961 - August 1961 | ||
| Caribbean / Recovery Mercury 4 "Liberty Bell 7" (21. July 1961) | ||
| VS-26 | S2F-2 | AV 00 |
| VS-36 | S2F-2 | AV 30 |
| VAW-12 Det. 36 | WF-2 | GE 00 |
| HS-7 | HSS-1N | AV 50 |
| HU-2 Det. 36 | HUP-3 | HU 00 |
| HMR(L)-262 | HUS-1 | ET 00 |
| CVS-15 USS Randolph | ||
| February 1962 - Februar 1962 | ||
| Caribbean / Recovery Mercury 6 ""Friendship 7 (20. Februar 1962) | ||
| VS-26 | S2F-2 | AV 00 |
| VS-36 | S2F-2 | AV 30 |
| VAW-12 Det. 15 | WF-2 | GE 00 |
| HS-7 | HSS-1N | AV 50 |
| CVS-15 USS Randolph | ||
| 7. June 1962 - 31. August 1962 | ||
| Mediterranean | ||
| VS-26 | S2F-2 | AV 00 |
| VS-36 | S2F-2 | AV 30 |
| VAW-12 Det. 15 | WF-2 | GE 00 |
| HS-7 | HSS-1N | AV 50 |
| HU-2 Det. 15 | HUP-3 | HU 00 |
| CVS-15 USS Randolph | ||
| 24. October 1962 - 7. November 1962 | ||
| Caribbean (Kuba) | ||
| VS-26 | S2F-2 | AV 00 |
| VS-36 | S2F-2 | AV 30 |
| VAW-12 Det. 15 | WF-2 | GE 00 |
| HS-7 | HSS-1N | AV 50 |
| CVS-15 USS Randolph | ||
| 23. November 1962 - 30. November 1962 | ||
| North Atlantic | ||
| VS-26 | S2F-2 | AV 00 |
| VS-36 | S2F-2 | AV 30 |
| VAW-12 Det. 15 | WF-2 | GE 00 |
| HS-7 | HSS-1N | AV 50 |
| CVS-15 USS Randolph | ||
| July 1963 - August 1963 | ||
| South Atlantic | ||
| VS-26 | S-2D | AV 00 |
| VS-36 | S-2D | AV 30 |
| VAW-12 Det. 15 | E-1B | GE 00 |
| HS-7 | SH-34J | AV 50 |
| CVS-15 USS Randolph | ||
| November 1963 - December 1963 | ||
| North Atlantic | ||
| VS-26 | S-2D | AV 00 |
| VS-36 | S-2D | AV 30 |
| VAW-12 Det. 15 | E-1B | GE 00 |
| HS-7 | SH-34J | AV 50 |
| CVS-15 USS Randolph | ||
| 22. January 1964 - 14. February 1964 | ||
| North Atlantic | ||
| VS-26 | S-2D | AV 00 |
| VS-36 | S-2D | AV 30 |
| VA-34 Det. 15 | A-4C | AC 300 |
| VAW-12 Det. 15 | E-1B | GE 700 |
| HS-7 | SH-3A | AV 50 |
| CVS-15 USS Randolph | ||
| March 1964 - August 1964 | ||
| North Atlantic | ||
| VS-26 | S-2D | AV 00 |
| VS-36 | S-2D | AV 30 |
| VAW-12 Det. 15 | E-1B | GE 00 |
| HS-7 | SH-3A | AV 50 |
| CVS-11 USS Intrepid | ||
| November 1964 - December 1964 | ||
| North Atlantic | ||
| VS-26 | S-2D | AV 00 |
| VS-36 | S-2D | AV 30 |
| VAW-12 Det. 11 | E-1B | GE 00 |
| HS-7 | SH-3A | AV 50 |
| CVS-15 USS Randolph | ||
| February 1965 - May 1965 | ||
| North Atlantic | ||
| VS-26 | S-2D | AV 00 |
| VS-36 | S-2D | AV 30 |
| VAW-12 Det. 15 | E-1B | GE 00 |
| HS-7 | SH-3A | AV 50 |
| CVS-15 USS Randolph | ||
| July 1965 - August 1965 | ||
| Mediterranean | ||
| VS-26 | S-2D | AV 00 |
| VS-36 | S-2D | AV 30 |
| VAW-12 Det. 15 | E-1B | GE 00 |
| HS-7 | SH-3A | AV 50 |
| CVS-15 USS Randolph | ||
| January 1966 - March 1966 | ||
| North Atlantic | ||
| VS-26 | S-2D | AV 00 |
| VS-36 | S-2D | AV 30 |
| VS-39 Det. 15 | S-2D | AW 30 |
| VAW-12 Det. 15 | E-1B | GE 00 |
| HS-7 | SH-3A | AV 50 |
| HS-9 Det. 15 | SH-3A | AW 50 |
| 31. May 1966 CVSG-58 disestablished |
