During a gallop, there is a phase where all four legs are off the ground at the same time.
On this site
http://en.wikipedia.org/wiki/Gallop there is an animated gif which shows it and it then says:
In 1892, Leland Stanford settled an argument about whether galloping horses were ever fully airborne: he paid photographer Eadweard Muybridge to devise an apparatus with multiple trip wires attached to camera shutters. The photos, the first documented example of high-speed photography, clearly showed the horse airborne.