The aim of this work was twofold. First, an empirical study was designed aimed at investigating the perceptions that entry-level non-computing majors--namely Physical Education and Sport Science (PESS) undergraduate students--hold about basic Computer Literacy (CL) issues. The participants were 90 first-year PESS students, and their perceptions were elicited through a written questionnaire. The data analysis revealed scientifically acceptable perceptions as well as various empirical, vague, incomplete and erroneous perceptions. Second, those students' prior knowledge was utilized to design and implement an Educational Computer Card Game (ECCG) aimed at helping PESS students overcome their conceptual difficulties and approach the aforementioned CL issues in a scientifically consistent manner. The ECCG was designed taking into account basic digital game-based learning principles in combination with basic aspects of social and constructivist perspectives to learning. The ECCG was also pilot-tested in the field with real students, and the results were encouraging.