We report the discovery of a new double-image gravitational lens resulting from our search for lenses in the southern sky. Radio source PMN J2004-1349 is composed of two compact components separated by 1.13 arcseconds in VLA, MERLIN and VLBA images. The components have a flux ratio of 1:1 at radio frequencies ranging from 5 GHz to 22 GHz. The I-band optical counterpart is also an equal double, with roughly the same separation and position angle as the radio double. Upon subtraction of the components from the I-band image, we identify a dim pattern of residuals as the lens galaxy. While the present observations are sufficient to establish that J2004-1349 is a gravitational lens, additional information will be necessary (such as the redshifts of the galaxy and quasar, and precise astrometry and photometry of the lens galaxy) before constructing detailed mass models.