We report the discovery of a companion to the high proper motion star LHS 1589, a nearby high-velocity, low-mass subdwarf. The companion (LHS 1589B) is located 0.224+/-0.004" to the southwest of the primary (LHS 1589A), and is 0.5 magnitude fainter than the primary in the K_s band. The pair was resolved with the IRCAL infrared camera at Lick Observatory, operating with the Laser Guide Star Adaptive Optics system. A low-resolution spectrum of the unresolved pair obtained at the MDM observatory shows the source to be consistent with a cool subdwarf of spectral subtype sdK7.5. A photometric distance estimate places the metal-poor system at a distance d=81+/-18 parsecs from the Sun. We also measure a radial velocity V_rad=67+/-8 km/s which, together with the proper motion and estimated distance, suggests that the pair is roaming the inner Galactic halo on a highly eccentric orbit. With a projected orbital separation s=18.1+/-4.8 AU, and a crude estimate of the system's total mass, we estimate the orbital period of the system to be in the range 75 yr < P < 500 yr. This suggests that the dynamical mass of the system could be derived astrometrically, after monitoring the orbital motion over a decade or so. The LHS 1589AB system could thus provide a much needed constraint to the mass-luminosity relationship of metal-poor, low-mass stars. Comment: 6 pages, accepted for publication in the Astrophysical Journal. This revised version includes an expanded discussion and minor corrections