Se o teu telemóvel é relativamente recente e o vídeo foi apagado há pouco tempo, faz como o
@Ricardo_S7 indicou e verifica na Reciclagem (vai à Galeria, carrega nos 3 pontinhos e escolhe reciclagem).
Se não estiver lá, mas se estiveres a usar um cartão de memória, tira o cartão de memória do telemóvel e liga-o a um computador. Usa um programa de recuperação de dados (como o gratuito Recuva da Piriform, entre milhares de outros programas) e tenta recuperar o vídeo. Isto é tão mais provável quanto mais rápido o fizeres.
Se não tens cartão de memória e o vídeo não está na Reciclagem, então o melhor é desistir. Eu tentei instalar um dos programas mais conceituados na net para recuperar ficheiros, mas ele tentou fazer root ao telemóvel e estragou o sistema de ficheiros. Não consegui recuperar nada e tive que formatar o telemóvel, perdendo o resto dos dados. Por isso, mantém-te longe destes programas!