OKB-586 formed from a spin-off of portions of Sergei Korolev's OKB-1 production infrastructure under the direction of Mikhail Yangel in the early 1950s. Soon after, he started the development of an improved strategic missile that would outperform the R-5, SS-3 Shyster, that Korolev was in the process of bringing into production. Yangel's design was based on combining the basic airframe from the R-5 with an engine developed from the R-11 Zemlya. The R-11 was a short-range missile that used nitric acid as an oxidizer and kerosene as a fuel and could be stored for extended periods of time.
Valentin Glushko had long advocated using storable propellants, and proposed developing a new engine for the project. Earlier designs like the R-5 and R-7 used liquid oxygen as the oxidizer, and therefore had to be fueled immediately before launch, as the oxygen would "boil off" over time. He developed the RD-214 for the R-12, which consisted of four combustion chambers sharing a common turbopump assembly. The pumps were powered by decomposing the hydrogen peroxide, like earlier designs, to generate an exhaust. The new engine was too large to fit in the existing R-5 airframe, so a conical tail section was added to hold the engine.
Nikolay Pilyugin, head of the leading control system bureau, convinced Yangel to introduce a fully autonomous control system in the R-12 instead of the traditional radio control that had been used on earlier missiles. The R-5, for instance, used an inertial guidance system that had to be "fine tuned" by commands from ground radio stations that it passed over during its flight. Pilyugin felt that newer inertial systems would have the accuracy needed to hit targets at 2,000 km without the mid-course updates.
According to the official Yuzhnoye history, Yangel's design was approved on 13 February 1953 by the Council of Ministers of the USSR. However, another source reports that the approval was granted on 13 August 1955. The first test was conducted at Kapustin Yar on 22 June 1957. In September 1958, Nikita Khrushchev personally visited Kapustin Yar to witness the launch of R-12, as well as its competitor, the R-5M. The latter had already been accepted into deployment at the time. The R-12 launch was a success and the next month, mass production of the vehicle started in Dnepropetrovsk. Test launches continued until December and demonstrated a maximum error of 2.3 km.