We describe a Bayesian rejection sampling algorithm designed to efficiently compute posterior distributions of orbital elements for data covering short fractions of long-period exoplanet orbits. Our implementation of this method, Orbits for the Impatient (OFTI), converges up to several orders of magnitude faster than two implementations of MCMC in this regime. We illustrate the efficiency of our approach by showing that OFTI calculates accurate posteriors for all existing astrometry of the exoplanet 51 Eri b up to 100 times faster than a Metropolis-Hastings MCMC. We demonstrate the accuracy of OFTI by comparing our results for several orbiting systems with those of various MCMC implementations, finding the output posteriors to be identical within shot noise. We also describe how our algorithm was used to successfully predict the location of 51 Eri b six months in the future based on less than three months of astrometry. Finally, we apply OFTI to ten long-period exoplanets and brown dwarfs, all but one of which have been monitored over less than 3% of their orbits, producing fits to their orbits from astrometric records in the literature.