Given the current striving for "sustainability" and the corresponding paradigms shift in science, technology, R&D, environment perception, economy and politics; e.g., from unlimited growth-to-sustainable development, correction-to-prevention and passive consumption of "goods", culture and education--to active participation, primarily in the science-technology-environment-society-economy-policy (S-T-E-S-E-P) context, the corresponding paradigms shift, at all levels of education is unavoidable. This requires a paradigm shift in conceptualization, thinking, and research in science education, particularly concerning the science-technology-environment-society (STES) interfaces. Consequently, "STES literacy" requires the development of students' evaluative system thinking and transfer capabilities in this context via the corresponding innovative higher-order cognitive skills (HOCS)-promoting teaching assessment and learning strategies; meaning a shift, within different multicultural contexts, from the currently dominating lower-order cognitive skills (LOCS) algorithmic "teaching-to-know", to HOCS-promoting "learning-to-think", typified by students' capabilities of "critical evaluative system thinking" and "decision-making for problem solving and transfer". This should be consonant with innovative, interdisciplinary "generic, contextually bound", research-based teaching strategies and assessment methodologies leading to "HOCS learning". Our longitudinal research findings and application of this HOCS-promoting science education practice suggest that, although the road to STES literacy for sustainability is rocky, it is educationally doable and, therefore, attainable. (Contains 5 tables and 1 figure.)