In this work, we use battery impedance measurements from two publicly available datasets to propose and evaluate the performance of multiple models for temperature estimation. The datasets include Electrochemical Impedance Spectroscopy (EIS) experiments for two Nickel-Cobalt-Aluminium (NCA) cells, acquired under multiple temperature, State-of-Charge (SoC) and State-of-Health (SoH) conditions. Initially, through a correlation analysis, we identified the imaginary part of the impedance in the 100–1000 Hz range as the most suitable temperature indicator. Then, using a cross-validation approach, we evaluated the performance of several linear and non-linear models using the imaginary part at a single frequency as input. The performed analysis also considered the effects of including SoC and SoH dependencies in the models. We identified an exponential model using the imaginary part of the impedance at 800 Hz as the best performing single frequency model in terms of accuracy, which can be further improved by adding SoC information if available.