A primeira tarefa de Vasili Mishin, o sucessor de Sergei Korolev, como principal responsável do TsKBEM, foi a de determinar o estado do Programa Voskhod. Na altura do falecimento de Korolev, existiam planos para a realização de três ou quatro missões Voskhod e cinco missões Soyuz em 1966. A primeira missão, a Voskhod-3, seria uma missão de longa duração com os cosmonautas Boris Valentinovich Volynov e Georgi Stepanovich Shonin. O sucesso espectacular da missão de 14 dias da Gemini-VII em Dezembro de 1965 deu aos Soviéticos um ímpeto para arrancarem com esta missão que estava a ser planeada há já mais de um ano. Parece ter havido algum esforço por parte dos lideres ministeriais para substituir a missão que seria tripulada somente por cosmonautas femininos e na qual se realizaria uma actividade extraveícular, pela missão Voskhod-3. Porém, esta tentativa não foi frutuosa. A missão Voskhod-4 seria uma missão científica que iria incluir experiências de gravidade artificial com os cosmonautas Georgi Timofeyevich Beregovoi e Georgi Petrovich Katys, enquanto que a missão Voskhod-5 seria uma missão militar com os cosmonautas Vladimir Alexandrovich Shatalov e Lev Stepanovich Demin. Uma missão extra transportando cães, iria preceder a missão Voskhod-3 para testar os sistema de suporte de vida prolongada na quase obsoleta cápsula 3KV.
A missão Voskhod-3 havia sido planeada para coincidir com a abertura do 23º Congresso do Partido Comunista em princípios de Março de 1966, como uma ‘prenda’ para os guardiões doutrinários da União Soviética. Este voo, e as adicionais missões Voskhod, iriam também servir para encurtar a distância para a primeira missão Soyuz, na altura prevista para ter lugar em finais de 1966. A partir de uma perspectiva de relações públicas, as restantes expedições Voskhod iriam sem dúvida desviar as atenções mundiais das missões Gemini. Certamente, a missão da Voskhod-3, dedicada a retomar o recorde de permanência em órbita na altura detido pela Gemini-VII, seria uma vitória publicitária para o programa espacial Soviético.
A 27 de Janeiro de 1966, duas semanas após a morte de Korolev, Vasili Mishin dirigiu a primeira reunião técnica no OKB-1 durante a sua gestão para discutir as futuras missões Voskhod. Os participantes decidiram preparar o veículo Voskhod 3KV n.º 5 para ser lançada com dois cães a bordo na primeira metade de Fevereiro. Alguns dos militares, em particular Kamanin, opuseram-se a uma missão biomédica precursora de 30 dias, justificando que esta missão iria representar um atraso desnecessário para a missão Voskhod-3, que era muito importante para as futuras missões militares no espaço. Os cosmonautas haviam tido treinos prolongados na utilização de um instrumento de observação infravermelha denominado Svinets, que iria permitir observar os gases emitidos a partir de quatro mísseis balísticos. Ao mesmo tempo, os presentes decidiram lançar o veículo 3KV n.º 6 (Voskhod-3) numa missão de 18 dias entre 10 e 20 de Março de 1966 – isto é, após a aterragem da missão precursora. O principal factor limitativo para a missão prolongada parecia ser a fraca performance do sistema de suporte de vida da Voskhod, e em particular as suas capacidades de regeneração do ar, que a maior parte não acreditava ser capaz de garantir a segurança de dois cosmonautas em órbita por um longo período. Um segundo encontro similar a 1 de Fevereiro confirmou o estado geral de prontidão para levar a cabo o lançamento dos dois cães.
Não ocorreram atrasos significativos nos preparativos para o lançamento e a aprovação final foi dada pela Comissão Estatal a 17 de Fevereiro. Dois cães, seleccionados após um rigoroso processo de selecção levado a cabo no Instituto de Problemas Médicos e Biológicos de Moscovo, iriam voar uma missão de 25 dias. O veículo Voskhod 3KV n.º 5 foi lançado às 20:09:36UTC do dia 22 de Fevereiro de 1966 pelo foguetão 11A57 Voskhod (P15000-06) a partir do Complexo de Lançamento LC31/2 do Cosmódromo NIIP-5 Baikonur, tendo recebido a designação Cosmos-110 após entrar em órbita terrestre. A cápsula transportando os cães Veterok e Ugolek ficou colocada numa órbita elíptica com um perigeu a 187 km, apogeu a 904 km e inclinação orbital de 51,9º. O elevado apogeu orbital era uma evidente tentativa por parte dos cientistas soviéticos para examinarem os efeitos da cintura de radiações de Van Allen nos cães. Este foi um elemento do plano de voo que havia emergido originalmente em 1963 durante o planeamento do programa Vostok. A Comissão Estatal esperava lançar a subsequente missão Voskhod-3 para uma órbita similar não só para estudar os efeitos da radiação, mas também para reclamar o recorde absoluto de altitude para uma missão tripulada.
Enquanto que o principal objectivo da missão era o de testar o sistema de suporte de vida em preparação para a Voskhod-3, a missão do Cosmos-110 também incluía um número suplementar de objectivos científicos. Para além dos próprios cães, havia vários tipos de preparados de colheitas, amostras de soros sanguíneos, crescimento de proteínas e plantação de várias bactérias a bordo. Ao longo da missão os dois cães foram administrados com drogas anti-radiação e alimentos através de tubos directamente para o estômago. Veterok serviu como a cobaia experimental, enquanto que Ugolek era o animal de controlo. A 4 de Março a missão procedia sem problemas e a única situação registada foi a má abertura de uma das antenas de comunicações. A 14 de Março, a Comissão Estatal reuniu-se para decidir o progresso da missão. Apesar da condição dos cães e dos parâmetros da atmosfera da cabine, tais como pressão, temperatura, humidade e conteúdo de dióxido de carbono, se encontraram nos limites nominais, havia ocorrido uma tendência para a deterioração da composição do ar. Alguns recomendaram o final imediato da missão e a recuperação dos cães, enquanto que outros expressaram a sua confiança numa missão de 25 dias. Uma comissão especial de aterragem composta por vinte e cinco oficiais discutiu o assunto ao longo da noite e na manhã seguinte foi decidido iniciar as operações de recolha da missão. Os dois cães acabariam por aterrar no dia 16 de Março às 14:15UTC, a 210 km a sudeste de Saratov e a 60 km do local previsto de descida.
Eventualmente, a missão do Cosmos-110 seria o último voo do programa Voskhod devido aos problemas registados no sistema de suporte de vida e devido a outros problemas técnicos, nomeadamente na capacidade do sistema de pára-quedas de suportar o regresso de dois cosmonautas após uma missão prolongada e devido à falta de confiança no velho sistema que esticava perigosamente os limites das cápsulas, havendo também a necessidade de se transferir mão de obra necessária para o programa Soyuz.