The existence of the moons of Mars had been speculated about since the moons of Jupiter were discovered. It is known that when
Galileo, as a hidden report about him having observed two bumps on the sides of Saturn (later discovered to be its rings), used the anagram smaismrmilmepoetaleumibunenugttauiras for Altissimum planetam tergeminum observavi ("I have observed the most distant planet to have a triple form"),
Johannes Kepler had misinterpreted it to mean Salve umbistineum geminatum Martia proles (Hello, furious twins, sons of Mars).
Perhaps inspired by Kepler (and quoting
Kepler's third law of planetary motion),
Jonathan Swift's satire
Gulliver's Travels (1726) refers to two moons in Part 3, Chapter 3 (the "Voyage to
Laputa"), in which Laputa's astronomers are described as having discovered two satellites of Mars orbiting at distances of 3 and 5 Martian diameters with periods of 10 and 21.5 hours. The actual orbital distances of Phobos and Deimos are 1.4 and 3.5 Martian diameters, and their respective orbital periods are 7.66 and 30.35 hours.
 In the 20th century, V. G. Perminov, a spacecraft designer of early Soviet Mars and Venus spacecraft, speculated Swift found and deciphered records that Martians left on Earth.
 However, the view of most astronomers is that Swift was simply employing a common argument of the time, that as the inner planets Venus and Mercury had no satellites, Earth had one and Jupiter had four (known at the time), that Mars by analogy must have two. Furthermore, as they had not yet been discovered, it was reasoned that they must be small and close to Mars. This would lead Swift to making a roughly accurate estimate of their orbital distances and revolution periods. In addition Swift could have been helped in his calculations by his friend, the mathematician
Voltaire's 1752 short story "
Micromégas", about an alien visitor to Earth, also refers to two moons of Mars. Voltaire was presumably influenced by Swift.
 In recognition of these 'predictions', two craters on Deimos are named
 while on Phobos there is one named
regio, Laputa Regio, and one named
planitia, Lagado Planitia, both of which are named after places in Gulliver's Travels (the fictional
Laputa, a flying island, and
Lagado, imaginary capital of the fictional nation
 Many of the
craters on Phobos are also named after characters in Gulliver's Travels.
Asaph Hall discovered Deimos on 12 August 1877 at about 07:48
UTC and Phobos on 18 August 1877, at the
US Naval Observatory in
Washington, D.C., at about 09:14
GMT (contemporary sources, using the pre-1925 astronomical convention that began the day at noon, give the time of discovery as 11 August 14:40 and 17 August 16:06
Washington mean time respectively).
 At the time, he was deliberately searching for Martian moons. Hall had previously seen what appeared to be a Martian moon on 10 August, but due to bad weather, he could not definitively identify them until later.
Hall recorded his discovery of Phobos in his notebook as follows:
The telescope used to discover the Martian moons
- "I repeated the examination in the early part of the night of 11th [August 1877], and again found nothing, but trying again some hours later I found a faint object on the following side and a little north of the planet. I had barely time to secure an observation of its position when fog from the River stopped the work. This was at half past two o'clock on the night of the 11th. Cloudy weather intervened for several days.
- "On 15 August the weather looking more promising, I slept at the Observatory. The sky cleared off with a thunderstorm at 11 o'clock and the search was resumed. The atmosphere however was in a very bad condition and Mars was so blazing and unsteady that nothing could be seen of the object, which we now know was at that time so near the planet as to be invisible.
- "On 16 August the object was found again on the following side of the planet, and the observations of that night showed that it was moving with the planet, and if a satellite, was near one of its elongations. Until this time I had said nothing to anyone at the Observatory of my search for a satellite of Mars, but on leaving the observatory after these observations of the 16th, at about three o'clock in the morning, I told my assistant, George Anderson, to whom I had shown the object, that I thought I had discovered a satellite of Mars. I told him also to keep quiet as I did not wish anything said until the matter was beyond doubt. He said nothing, but the thing was too good to keep and I let it out myself. On 17 August between one and two o'clock, while I was reducing my observations, Professor Newcomb came into my room to eat his lunch and I showed him my measures of the faint object near Mars which proved that it was moving with the planet.
- "On 17 August while waiting and watching for the outer moon, the inner one was discovered. The observations of the 17th and 18th put beyond doubt the character of these objects and the discovery was publicly announced by Admiral Rodgers."
The telescope used for the discovery was the 26-inch (66 cm) refractor (telescope with a lens) then located at Foggy Bottom.
 In 1893 the lens was remounted and put in a new dome, where it remains into the 21st century.
The names, originally spelled Phobus and Deimus, respectively, were suggested by
Henry Madan (1838–1901), Science Master of
Eton, from Book XV of the
Ares summons Fear and Fright.
Mars moon hoax
Walter Scott Houston perpetrated a celebrated
April Fool's hoax in the April edition of the Great Plains Observer, claiming that "Dr. Arthur Hayall of the University of the Sierras reports that the moons of Mars are actually artificial satellites". Both Dr. Hayall and the University of the Sierras were fictitious. The hoax gained worldwide attention when Houston's claim was repeated in earnest by a Soviet scientist,
 who, based on a later-disproven density estimate,
suggested Phobos was a hollow metal shell.
Searches have been conducted for additional satellites. Most recently,
Scott S. Sheppard and
David C. Jewitt surveyed the
Hill sphere of Mars for irregular satellites. The search covered nearly the entire Hill sphere, but scattered light from Mars excluded the inner few arcminutes where the satellites Phobos and Deimos reside. No new satellites were found to an apparent limiting red magnitude of 23.5, which corresponds to radii of about 0.09 km using an albedo of 0.07.