Presently, computational thinking (CT) is considered necessary for adapting to the future. Concurrently, the COVID-19 pandemic has accentuated the demand for strengthening Environmental Education as a means to improve sustainability and stimulate environmental protection and public health. Having in mind that CT does not concern only technocrats but also applies in solving everyday problems, we introduce the novel idea of the synergistic learning of CT and Environmental Study. Thus, our research aim is to explore the correlation between algorithmic thinking (AT), as a fundamental CT competency, and educational achievements in the Environmental Study course during the early primary school years. Towards this end, we implemented a quantitative research study, employing an innovative assessment framework we propose. The adoption of cluster sampling eventuated in a sample of 435 students. The exploitation of ordinal logistic regression analysis and machine learning method validated the correlation of the two fields and pointed out that AT levels constitute a predictive factor for performance in the Environmental Study course and vice versa. These results support the novel idea of concurrently cultivating environmental consciousness and CT and build a robust base for future studies that will focus on providing an ecological reflection on CT activities.