PSR J0636+5128 is a millisecond pulsar in one of the most compact pulsar binaries known, with a 96 minute orbital period. The pulsar mass function suggests a very low mass companion, similar to that seen in so-called black widow binaries. Unlike in most of those, however, no radio eclipses by material driven off from the companion were seen leading to the possibility that the companion was a degenerate remnant of a carbon-oxygen white dwarf. We report the discovery of the optical counterpart of its companion in images taken with the Gemini North and Keck I telescopes. The companion varies between r' = 25 and r' = 23 on the 96 minute orbital period of the binary, caused by irradiation from the pulsar's energetic wind. We modeled the multicolor light curve using parallax constraints from pulsar timing and determine a companion mass of (1.71 +/- 0.23) x 10(-2) M-circle dot,M- a radius of (7.6 +/- 1.4) x 10(-2) R-circle dot, and a mean density of 54 +/- 26 g cm(-3), all for an assumed neutron star mass of 1.4 M-circle dot. This makes the companion to PSR J0636+5128 one of the densest of the black widow systems. Modeling suggests that the composition is not predominantly hydrogen, perhaps due to an origin in an ultracompact X-ray binary.