In positron emission tomography (PET) and single photon emission tomography (SPECT), attenuation correction is necessary for quantitative reconstruction of the tracer distribution. Previously, several attempts have been made to estimate the attenuation coefficients from emission data only. These attempts had limited success, because the problem does not have a unique solution, and severe and persistent "cross-talk" between the estimated activity and attenuation distributions was observed. In this paper, we show that the availability of time-of-flight (TOF) information eliminates the cross-talk problem by destroying symmetries in the associated Fisher information matrix. We propose a maximum-a-posteriori reconstruction algorithm for jointly estimating the attenuation and activity distributions from TOF PET data. The performance of the algorithm is studied with 2-D simulations, and further illustrated with phantom experiments and with a patient scan. The estimated attenuation image is robust to noise, and does not suffer from the cross-talk that was observed in non-TOF PET. However, some constraining is still mandatory, because the TOF data determine the attenuation sinogram only up to a constant offset.