In order to guarantee safe and proper use of Lithium-ion batteries during operation, an accurate estimate of the (internal) battery temperature is of paramount importance. Electrochemical impedance spectroscopy (EIS) can be used to estimate the (internal) 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 temperature estimation methods implicitly distinguish two steps: experiment design and parameter estimation. The former step consists of choosing the excitation frequency (or frequencies) and the latter step consists of estimating the battery temperature based on the measured impedance resulting from the chosen excitation(s). By distinguishing these steps and by performing Monte-Carlo simulations, all existing estimation methods are compared in terms of accuracy (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 temperature 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. This novel more-accurate method estimates the temperature with an rms bias of 0.4 degree Celsius and an average standard deviation of 0.7 degree Celsius using a single impedance measurement for the battery under consideration.