We report the discovery of strong soft X-ray emission lines and a hard continuum above 2 keV in the Narrow-Line Seyfert 1 galaxy Mrk 335 during an extremely low X-ray flux state. Mrk 335 was observed for 22 ks by XMM-Newton in July 2007 as a Target of Opportunity to examine it in its X-ray low-flux state, which was discovered with Swift. Long-term light curves suggest that this is the lowest flux state this AGN has ever been seen in. However, Mrk 335 is still sufficiently bright that its X-ray properties can be studied in detail. The X-ray continuum spectrum is very complex and requires several components to model. Statistically, partial covering and blurred reflection models work well. We confirm the presence of a strong narrow Fe line at 6.4 keV. High-resolution spectroscopy with the XMM-RGS reveals strong, soft X-ray emission lines not detected in previous, higher signal-to-noise, XMM-Newton observations, such as: highly ionized Fe lines, O VII, Ne IX and Mg XI lines. The optical/UV fluxes are similar to those previously measured with Swift. Optical spectroscopy taken in 2007 September do not show any changes to optical spectra obtained 8 years earlier. Comment: Accepted for publication in ApJ; 26 pages, 10 figues, in press, ApJ 681 (July 01, 2008); Updated version with corrections made by the editor