The overwhelming success of the commercial game market has brought increased attention to emerging work in educational game design. Much of the existing work in educational games a strong similarity to the field of Problem-Based Learning (PBL), which has a rich history of conceptual literature as well as empirical investigations. Despite apparent similarities between the two fields, there has been no formal effort to explore the connections between them. This conceptual paper examines the basic tenants of PBL with an eye toward making prescriptive recommendations for the design and use of problem-based educational games. Examples within existing educational games are discussed in the context of PBL features and outcomes.