En avril 1962, alors que le programme Vostok confère à l'Union soviétique toujours plus de prestige en accumulant les succès, les autorités du Parti communiste donnent leur feu vert au développement du vaisseau Soyouz, appelé à prendre sa relève. Un problème se pose alors, car les vols Vostok doivent prendre fin en 1963, et le Soyouz ne sera pas prêt avant 1965 au plus tôt. Sergueï KOROLIOV assigne pour tâche à une cinquantaine de ses ingénieurs de modifier le vaisseau Vostok-3KA pour lui permettre de réaliser quelques missions supplémentaires durant cette période (vols Vostok 7 à Vostok 10).

Mais une mauvaise nouvelle ne tarde pas à arriver : les Américains ont annoncé qu'ils feront voler leur nouveau vaisseau Gemini dès 1964. Gemini sera capable d'effectuer des manoeuvres de rendez-vous et d'amarrage en orbite, offrira la capacité de sorties extravéhiculaires (EVA) et pourra embarquer deux cosmonautes. Il est clair que le Vostok-3KA, même modifié, ne sera pas en mesure de répondre à de telles performances. Le 4 février 1964, le Parti communiste met fin à tous les travaux concernant le programme Vostok. Il donne aussi l'ordre à KOROLIOV de suspendre ses travaux sur Soyouz afin de se concentrer sur la préparation d'un vaisseau dérivé du Vostok capable d'emmener trois hommes dans l'Espace, et ce pendant l'année en cours, de façon à devancer les vols Gemini.

Les ingénieurs de l'OKB-1 sont très récalcitrants vis-à-vis de ce projet, car il est évident que sa mise en oeuvre nécessitera l'abandon de nombreux systèmes dédiés à la sécurité de l'équipage. En février 1964 KOROLIOV décide de remettre ses ingénieurs au pas. Il leur annonce que si le projet aboutit, une place à bord du vaisseau sera réservée à l'un d'eux. Ils se mettent alors très vite au travail...

Dès le 4 février 1964 quatre cosmonautes du TsPK-1, et aussi un du TsPK-2, sont détachés sur ce programme. Il s'agit de BELIAÏEV, BEREGOVOÏ, KHROUNOV, KOMAROV et LEONOV.

Le 13 mars 1964, une réunion de la Commission Militaro-Industrielle (VPK) officialise l'adoption du projet en signant le décret n°59, et le baptise Voskhod (lever de Soleil). La Commission préconise un premier lancement en août 1964, soit dans un délai de cinq mois. De plus, elle fixe un objectif secondaire à KOROLIOV : celui de réaliser une sortie dans l'Espace. L'OKB-1 avait déjà réfléchi à cette question dans le cadre des missions des Vostok modifiés, et avait baptisé ce projet Vikhod (sortie). Ce nom est réutilisé et c'est ainsi que sera désigné le nouveau projet. Le 1er avril 1964, les cosmonautes du TsPK-1 BIKOVSKI, POPOVITCH et TITOV sont à leur tour assignés au programme.

Le 13 avril 1964, le Parti communiste signe le décret autorisant le démarrage des travaux de construction de trois Voskhod et deux Vikhod. Au passage, les capsules destinées au programme Voskhod sont appelées 3KV, et celles destinées au programme Vikhod sont appelées 3KD. Le 23 avril, les cosmonautes VOLINOV (TsPK-1) et DIOMINE (TsPK-2) rejoignent le groupe qui s'entraîne pour voler sur Voskhod ou Vikhod.