Millisecond pulsars are thought to be neutron stars that have been spun-up by accretion of matter from a binary companion. Although most are in binary systems, some 30% are solitary, and their origin is therefore mysterious. PSR J1719-1438, a 5.7 ms pulsar, was detected in a recent survey with the Parkes 64m radio telescope. We show that it is in a binary system with an orbital period of 2.2 h. Its companion's mass is near that of Jupiter, but its minimum density of 23 g cm$^{-3}$ suggests that it may be an ultra-low mass carbon white dwarf. This system may thus have once been an Ultra Compact Low-Mass X-ray Binary, where the companion narrowly avoided complete destruction.