In the mid- to late 1950's the Soviet Union embarked on a rapid missile development program.  This was largely a result of policy changes made by Nikita Khrushev, who believed that conventional wars would be a thing of the past in the face of nuclear weapons.  His view led the Soviets away from the massed formations of tanks and men that they had used in the Great Patriotic War.  The new weapons of choice would be missiles, bombers, and missile armed submarines - all with nuclear weapons.

The decree that led to the creation of the R-12 missile (the Soviet designation for the SS-4) was issued in 13 August 1953.  It was the first Soviet strategic missile that used storable propellants.  The design process was difficult, but by 12 July 1957 the first R-12 missile was launched from the Kaputsin Yar research center.  Two of the missiles were sold to China in August of that year.  Silo based launches with the missile were undertaken for the first time in September from the same test center.

These tests were deemed to be successful and on 4 March 1959 the R-12 was adopted as the new medium range ballistic missile.  All of these missiles were surface launched.  In May 1960 many of the missiles began to be based in hardened silos.   These silo launched missile complexes were composed of four launchers.  These early missiles used radio command guidance to reach their target.  Later versions used an inertial guidance system.  There were plans for a railroad based version of the missile, but these plans were suspended.

  The first five regiments of surface based missiles were put on alert in mid-May 1960 shortly after an American U-2 pilot was shot down on a spy mission over the Soviet Union.  Western observers first saw the R-12 in November of 1960 it was designated the SS-4 'Sandal'.

In 1961 a modified SS-4 was introduced called the SS-5 'Skean'.  It had a longer range, but was not judged to be a significant improvement and production was limited.  On 1 November of the following year an SS-4 was launched with a live nuclear warhead from the Baikonur test center.  Its one megaton warhead detonated successfully in the Semipalatinsk region.

The SS-4 'Sandal' was first deployed to Cuba in the Fall of 1962.  This led to the international dispute known as the Cuban Missile Crisis.  The missiles were later removed from Cuba in exchange for the United States removing its Jupiter II missiles from its bases in Turkey.  It is also interesting to note that one regiment of silo based missiles went on alert in early January of 1963.

The SS-4 was also used in more peaceful pursuits such as space exploration.  In 1963 they were used in an experiment by the Chelomei design team.  Still, the primary use of the SS-4 was as a weapon and in 1964 the missile was modified and designated the R-12U.  The new version was immediately accepted for military service.

The highest number of SS-4 'Sandal' missiles in service was 608 in 1964.  By 1968 the Soviet military began to phase out some of the missiles based in 'soft sites' with some 'hard sites' being phased out in 1972.  The beginning of the end of the SS-4 'Sandal' was in 1978 when they began to be phased out in favor of mobile SS-20 IRBM systems.  By 1980 there were approximately 500 of the missiles in service.  

The SS-4 'Sandal' was the first Soviet strategic missile that used storable propellants and a completely autonomous inertial guidance system.  It was designed to target cities and other strategic targets in China and Europe with its single megaton range warhead.  It formed the largest part of the Soviet threat to Western Europe during the Cold War.