We report the discovery of two well-defined tidal tails emerging from the sparse remote globular cluster Palomar 5. These tails stretch out symmetrically to both sides of the cluster in the direction of constant Galactic latitude and subtend an angle of 2.6 degrees on the sky. The tails have been detected in commissioning data of the Sloan Digital Sky Survey (SDSS), providing deep five-color photometry in a 2.5 degrees wide band along the equator. The stars in the tails make up a substantial part (~1/3) of the current total population of cluster stars in the magnitude interval 19.5 < i* < 22.0. This reveals that the cluster is subject to heavy mass loss. The orientation of the tails provides an important key for the determination of the clusters Galactic orbit.