Utilizing interpretable machine learning techniques that exhibit both predictive and informative capabilities enables the effective discovery of high-performance materials. In this study, the potential of the sure-independence screening and sparsifying operator (SISSO) method is explored for the development of multicomponent catalysts for propane dehydrogenation (PDH). For cost-effectiveness and wide applicability, we trained SISSO models using a small laboratory-scale database with easily accessible atomic properties of the elements, elemental loading, preparation conditions, and reaction conditions. The optimal SISSO model for predicting the propylene yield (Y) was selected based on the model fit and simplicity of the resulting formulas. The informative formula provided guidelines for the design of three active component catalysts for PDH. The experimental validation of the catalysts demonstrated the reliability of the SISSO model. More importantly, SISSO predictions successfully led to the discovery of new high-performance PDH catalysts based on Ga, Pt, and P. Compared with the catalysts in the collated database, the catalysts proposed by SISSO consisted of a different combination of components and showed superior Y values. This study highlights the potential of interpretable machine learning in providing essential guidance for discovering new heterogeneous catalysts through the utilization of a small database containing easily available atomic properties.