In the context of curricular history education both commercial entertainment games as well as serious games specifically tailored for educational purposes were employed. Especially the latter types of games were reported as being promising concerning instructional effectiveness. Still, there are not many complex serious games for history education, particularly in the secondary schools context. In this work-in-progress paper, we report on the progress of project Stories from the History of Czechoslovakia, a serious game for teaching history of the Czech lands in the 20th century. We introduce main game concepts, describe two main design challenges we have been facing during the development and how we have addressed them and overview our feasibility study on 71 high-school students. This paper can be informative for researchers and designers working on similar projects.