Sugar-based surfactants are renewable alternatives to petroleum-based surfactants in many applications such as detergents and cosmetics. However, their molecular structure often gives rise to relatively stable crystals, which can lead to difficulties in dissolving them in water. This phenomenon is characterized by the Krafft temperature (T K), above which the surfactant solubility becomes high enough to induce self-association into micelles. Small changes in the molecular structure can result in large T K differences, which make rationalization and prediction of T K challenging. Few models were proposed in the literature, but none of them are applicable to sugar-based surfactants. In this article, we propose two decision tree models to estimate whether sugar-based surfactants exhibit potential dissolution issues at room temperature (i.e., T K above 25 °C or not). The first one, based on the descriptors of the whole molecule including quantum-chemical ones, was able to correctly classify 86% of the surfactants in the validation set. The second one, built from simple structural counts of the polar headgroup and the alkyl chain, could predict the right class for 78% of the surfactants in the validation set. These classification models account for experimentally known trends between the molecular structure and T K, such as the impact of the polar headgroup size, the alkyl chain length, and the presence of an amide linkage. To the end, our models were applied to a practical case to show how they can help in designing synthesis procedures of new surfactants.