Within the next few years, Advanced LIGO and Virgo should detect gravitational waves from binary neutron star and neutron star-black hole mergers. These sources are also predicted to power a broad array of electromagnetic transients. Because the electromagnetic signatures can be faint and fade rapidly, observing them hinges on rapidly inferring the sky location from the gravitational-wave observations. Markov chain Monte Carlo methods for gravitational-wave parameter estimation can take hours or more. We introduce BAYESTAR, a rapid, Bayesian, non-Markov chain Monte Carlo sky localization algorithm that takes just seconds to produce probability sky maps that are comparable in accuracy to the full analysis. Prompt localizations from BAYESTAR will make it possible to search electromagnetic counterparts of compact binary mergers.