In the digital era, pupils in primary and secondary schools tend to be familiar with smartphones, PDAs, tablets, GPS navigators etc. Since mobile devices provide new opportunities for teaching and learning, it is necessary to look for an effective way of using them in the curriculum. In this paper, the location-based games are presented as a tool for producing innovative learning scenarios. The potential of location-based games is analyzed as for their contribution to the Informatics education. The constructivist and constructionist attributes of learning that occurs while playing or developing such games are pointed out. The idea of playing location-based games to introduce some fundamental Informatics concepts is supported through a case study. The involved pupils (aged 10-15) have never played a location-based game before. Reported findings are grounded in observations and interviews with participants.