In the course of a Cycle 8 snapshot survey, we have discovered that the z=1.565 quasar HE 0512-3329 is a double with image separation 0.644", almost certainly due to gravitational lensing. The two components differ in brightness by only 0.4 magnitudes and a high signal-to-noise ground-based composite optical spectrum shows no trace of any stellar features at zero redshift, essentially ruling out the possibility that one of the two components is an ordinary Galactic star. The optical spectrum shows strong absorption features of MgII, MgI, FeII, FeI, and CaI, all at an identical intervening redshift of z=0.9313, probably due to the lensing object. The strength of the MgII and the presence of the other low ionization absorption features is strong evidence for a damped Lyman alpha system, likely the disk of a spiral galaxy. Point spread function fitting to remove the two quasar components from the STIS image leads to a tentative detection of a third object which may be the nucleus of the lensing galaxy. The brighter component is significantly redder than the fainter, due to either differential extinction or microlensing.

AASTEX preprint format, 11 pages, 3 figures; accepted by the Astronomical Journal; replaced with revised, accepted version