Halibut had been originally constructed as a carrier for the Regulus cruise missile. Regulus was a strategic missile, designed for nuclear attacks on Soviet bases. However, it required active guidance, meaning that the launching submarine would have to remain surfaced (and sending radio messages that broadcasted its position) until the missile hit its target, making the sub an easy target. Regulus could also be targeted by Soviet air defences, and needed a degree of preparation on the surface before it could be launched. These disadvantages meant that it was soon replaced by submarine-launched ballistic missiles, which could be launched while submerged, needed no preparation or guidance, and could not be easily intercepted. Regulus exited service in 1964. This left the USN with five submarines with the large hangars required to house the Regulus missile. Two were decommissioned (one is now a museum, while the other was expended as a target), and two more were converted to transports for special forces troops. Halibut was the fifth.

In 1965, she would be converted to a special missions submarine. The Pentagon had interests in being able to study and recover objects on the seafloor, under a project known as 'Sand Dollar'. This would allow them to gather intelligence into Soviet capabilities by studying things like rocket parts that had fallen into the ocean, as well as recovering American equivalents to prevent the Soviets studying them too. There were American assets that could do this. The bathyscaph Trieste II and the research ship Mizar could both photograph the seabed, the former by visiting it directly, and the latter using towed cameras and sonars. However, neither could be covert. The Soviets were aware of the capabilities of both vessels, and could easily track and follow them on the surface (Trieste needed significant support from surface craft). Halibut offered a solution; as a submarine, she could not be easily tracked. Her refit to her new purpose lasted seven months, from February-September 1965. Her sail was rebuilt to house more sensor masts, she was given a darkroom to develop photos, and most importantly, her hangar was completely rebuilt for special missions. The most important component of this was the capability to launch, tow and recover a sensor sled - the 'Fish'. The Fish was a two-tonne, twelve-foot long device, carrying sonars, cameras and lights. It could survive depths up to 20,000 feet, while being towed on a tow cable of ~25,000 feet. This allowed the submarine to photograph objects on the seabed, while remaining at just 200 feet below the sea's surface. The Fish was designed to be towed for six days at a time. Then it would be hoisted in, the film in its cameras changed and developed, and its batteries recharged.

The Fish was used to photograph K-129 in April-May 1968. It was a multi-phase operation. First, the submarine planted a grid of acoustic transponders over the area to be searched. These small devices, launched from the sub's torpedo tubes, would sink to the bottom, and return a sonar 'ping' when Halibut's sonar pinged them. Each transponder would respond to a unique sonar ping, so this grid allowed Halibut to find her position very accurately. This process took 36 hours. Then, the submarine began to search the area with the Fish, using its sonars to map the seabed and identify points of interest. Once these had been mapped, she imaged these in detail, until she found K-129. Roughly 20,000 photos were taken in the area of K-129, of which 9,000 showed her wreckage.