In this paper, we present a new methodology for the simultaneous retrieval of surface and atmospheric parameters of Mars. The methodology is essentially based on similar codes implemented for high-resolution instruments looking at Earth, supported by a statistical retrieval procedure used to initialize the physical retrieval algorithm with a reliable first guess of the atmospheric parameters. The methodology has been customized for the Thermal Emission Spectrometer (TES), which is a low-resolution interferometer. However, with minor changes to the forward and inverse modules, it is applicable to any instrument looking at Mars, and with particular effectiveness to high-resolution instruments. The forward module is a monochromatic radiative transfer model with the capability to calculate analytical Jacobians of any desired geophysical parameter. In the present work, we describe the general methodology and its application to a large sample of TES spectra. Results are drawn for the case of surface temperature and emissivity, atmospheric temperature profile, water vapor, and dust and ice mixing ratios. Comparison with climate models and other TES data analyses show very good agreement and consistency.