PSR J1024-0719 is a millisecond pulsar that was long thought to be isolated. However, puzzling results concerning its velocity, distance, and low rotational period derivative have led to a reexamination of its properties. We present updated radio timing observations along with new and archival optical data which show that PSR J1024-0719 is most likely in a long-period (2-20 kyr) binary system with a low-mass (approximate to 0.4 M-circle dot), low-metallicity (Z approximate to -0.9 dex) main-sequence star. Such a system can explain most of the anomalous properties of this pulsar. We suggest that this system formed through a dynamical exchange in a globular cluster that ejected it into a halo orbit, which is consistent with the low observed metallicity for the stellar companion. Further astrometric and radio timing observations such as measurement of the third period derivative could strongly constrain the range of orbital parameters.