Asaph Hall descobriu Deimos em 12 de agosto de 1877, por volta das 07.48 UTC, e Phobos em 18 de agosto de 1877, no Observatório Naval dos Estados Unidos em Washington, DC, por volta das 09.14 GMT (fontes contemporâneas, usando a convenção astronómica pré-1925 que começou o dia ao meio-dia, dá a hora da descoberta como 11 de agosto 14.40 e 17 de agosto 16.06 (hora média de Washington, respetivamente). Na época, ele estava deliberadamente procurando por luas marcianas. Hall já tinha visto o que parecia ser uma lua marciana em 10 de agosto, mas devido ao mau tempo, ele não pôde identificá-los definitivamente até mais tarde.
Hall registou a sua descoberta de Fobos em seu caderno da seguinte forma:
"Repeti o exame na parte inicial da noite de 11 [de agosto de 1877], e novamente não encontrei nada, mas tentando novamente algumas horas depois, encontrei um objeto tênue no lado seguinte e um pouco ao norte do planeta. hora de garantir uma observação da sua posição quando o nevoeiro do Rio interrompeu os trabalhos, isto foi às duas e meia da noite do dia 11. O tempo nublado interveio durante vários dias."Em 15 de agosto o tempo parecia mais promissor, dormi no Observatório. O céu clareou com uma tempestade às 11 horas e a busca foi retomada. A atmosfera, entretanto, estava em muito mau estado e Marte estava tão escaldante e instável que nada podia ser visto do objeto, que agora sabemos que estava naquela época tão perto do planeta que era invisível. “Em 16 de agosto o objeto foi encontrado novamente no lado seguinte do planeta, e as observações daquela noite mostraram que ele estava se movendo com o planeta, e se um satélite, estava perto de um de seus alongamentos. Até este momento eu não havia dito nada a ninguém no Observatório da minha busca por um satélite de Marte, mas ao deixar o observatório após as observações do dia 16, por volta das três da manhã, contei ao meu assistente, George Anderson, a quem havia mostrado o objeto, que pensei ter descoberto um satélite de Marte. Disse-lhe também para ficar calado, pois não queria que nada fosse dito até que o assunto estivesse fora de dúvida. Ele não disse nada, mas a coisa era boa demais para se guardar. Em 17 de agosto, entre a uma e as duas horas, enquanto eu reduzia minhas observações, o Professor Newcomb entrou em meu quarto para almoçar e eu mostrei a ele as minhas medidas do objeto fraco perto de Marte, o que provou que ele estava se movendo com o planeta.
"Em 17 de agosto, enquanto esperava e observava a lua externa, a interna foi descoberta. As observações dos dias 17 e 18 colocaram fora de dúvida o caráter desses objetos e a descoberta foi anunciada publicamente pelo almirante Rodgers."
Visto de Deimos, Marte surge no céu como um objeto 1000 vezes maior e 400 vezes mais brilhante do que a Lua cheia, como é observada da Terra.
Visto de Marte, Deimos surge como um pequeno ponto no céu, difícil de distinguir dos outros astros embora, no seu máximo brilho, possua um brilho equivalente a Vénus (tal como é visto da Terra).
Uma missão de retorno de amostras chamada "Gulliver" foi conceptualizada. Basicamente, um quilograma de material de Deimos seria trazido para a Terra nessa missão.
