To overcome the premature convergence and limited local search capability of conventional simulated annealing (SA) algorithm, this study proposes an improved multi-start adaptive simulated annealing (MAR-SA) algorithm. MAR-SA integrates a multi-start search mechanism, adaptive step-size control, and stagnation-triggered local re-finement to strengthen both global exploration and local exploitation. In terahertz thickness inversion experiments, MAR-SA achieves a correlation coefficient of 0.999 with the measured signals and consistently outperforms the conventional SA algorithm on three thin-film samples with different materials and thicknesses. Compared with SA, the mean relative errors (MREs) are reduced to 3.55%, 2.93%, and 1.63% for the 50 μm polyethylene terephthalate (PET), 60 μm poly-propylene (PP), and 75 μm polyethylene naphthalate (PEN) samples, respectively. The proposed algorithm provides a robust and high-precision solution for nondestructive THz coating thickness evaluation and demonstrates strong potential for practical engineering applications.