We present near-infrared and optical observations of the field of the Anomalous X-ray Pulsar 1E 2259+58.6 taken with the Keck telescope. We derive a subarcsecond Chandra position and tie it to our optical reference frame using other stars in the field. We find a very faint source, Ks = 21.7pm0.2 mag, with a position coincident with the Chandra position. We argue that this is the counterpart. In the J, I, and R bands, we derive (2 sigma) limits of 23.8, 25.6 and 26.4 mag, respectively. As with 4U 0142+61, for which a counterpart has previously been found, our results are inconsistent with models in which the source is powered by accretion from a disk, but may be consistent with the magnetar model.