In order to guarantee safe and proper use of Lithium-ion batteries during operation, an accurate estimate of the battery temperature is of paramount importance. Electrochemical Impedance Spectroscopy (EIS) can be used to estimate the battery temperature and several EIS-based temperature estimation methods have been proposed in the literature. In this paper, we argue that all existing EIS-based methods implicitly distinguish two steps: experiment design and parameter estimation. The former step consists of choosing the excitation frequency and the latter step consists of estimating the battery temperature based on the measured impedance resulting from the chosen excitation. By distinguishing these steps and by performing Monte-Carlo simulations, all existing methods are compared in terms of accuracy (i.e., mean-square error) of the temperature estimate. The results of the comparison show that, due to different choices in the two steps, significant differences in accuracy of the estimate exist. More importantly, by jointly selecting the parameters of the experiment-design and parameter-estimation step, a more-accurate temperature estimate can be obtained. In case of an unknown State-of-Charge, this novel method estimates the temperature with an average absolute bias of 0.4°C and an average standard deviation of 0.7°C using a single impedance measurement for the battery under consideration