Innovation plays a pivotal role in shaping structural change and advancing sustainable development. However, cross-country evidence regarding how innovation interacts with the economic, social, and environmental dimensions of sustainability remains fragmented and heterogeneous. Rather than assuming universally homogeneous relationships, this study conceptualizes the innovation–sustainability nexus as structurally contingent and conditioned by countries’ development stages and broader structural characteristics. Accordingly, the study does not seek to estimate universal causal effects, but rather to identify heterogeneous structural configurations across economies. To this end, an interpretable machine-learning segmentation approach based on the model tree algorithm is applied using data from 129 countries and international indicators, including the Global Innovation Index (GII), SDG Index, GDP growth, GDP per capita (PPP), and greenhouse gas emissions. The model tree framework combines recursive decision-tree partitioning with local linear regression models, enabling the identification of endogenous structural regimes and context-specific association patterns. The results reveal substantial cross-country heterogeneity. In some structural regimes, innovation performance is strongly associated with income levels and sustainability outcomes, whereas in others, structural constraints and developmental challenges shape differentiated innovation trajectories with limited explanatory consistency. These findings suggest that the innovation–sustainability nexus is not governed by a universally stable relationship, but rather mediated by development conditions and structural characteristics of national innovation systems. The study contributes to the literature by documenting macro-level heterogeneity and demonstrating the analytical value of interpretable segmentation methods for comparative sustainability research.