The unfolding or melting temperature (TM) is a central quantity to characterize the stability of proteins and other biopolymers. The accurate prediction of protein melting temperatures by molecular mechanics force field simulations is highly desirable for many biophysical and biotechnological applications. Since the time scales for protein (un)folding are hardly accessible in conventional molecular dynamics simulations, enhanced sampling techniques such as Temperature Replica Exchange Molecular Dynamics (TREMD) are typically employed. However, TREMD simulations are computationally very demanding, especially if large temperature ranges need to be covered. In addition, if TM is initially unknown, setting up TREMD simulations is often challenging. To find the optimal initial conditions for such simulations, we describe their performance using a theoretical model, which we validate on a minimalistic Markov chain Monte Carlo simulation setup. In an effort to reduce the computational demand, we have investigated the possibility of using small sets of TREMD temperature ladders placed iteratively in the vicinity of a TM estimate. Different TREMD setups were extensively tested on the fast-folding protein chignolin. We found that appropriate starting conformations lead to significantly faster convergence. Furthermore, we found that, in practice, combining multiple small temperature ladders can be advantageous in comparison to a single temperature ladder. Based on our findings, we formulate practical recommendations on how to setup TREMD for protein melting with optimal efficiency.