Enzymatic decarboxylation of biobased hydroxycinnamic acids gives access to phenolic styrenes for adhesive production. Phenolic acid decarboxylases are proficient enzymes that have been applied in aqueous systems, organic solvents, biphasic systems, and deep eutectic solvents, which makes stability a key feature. Stabilization of the enzyme would increase the total turnover number and thus reduce the energy consumption and waste accumulation associated with biocatalyst production. In this study, we used ancestral sequence reconstruction to generate thermostable decarboxylases. Investigation of a set of 16 ancestors resulted in the identification of a variant with an unfolding temperature of 78.1 °C and a half-life time of 45 h at 60 °C. Crystal structures were determined for three selected ancestors. Structural attributes were calculated to fit different regression models for predicting the thermal stability of variants that have not yet been experimentally explored. The models rely on hydrophobic clusters, salt bridges, hydrogen bonds, and surface properties and can identify more stable proteins out of a pool of candidates. Further stabilization was achieved by the application of mixtures of natural deep eutectic solvents and buffers. Our approach is a straightforward option for enhancing the industrial application of the decarboxylation process.