In daily patient-history taking and diagnosis practice, doctors ask questions to gather information from patients and narrow down diagnostic hypotheses. Training medical students to be efficient problem solvers through the use of questioning is therefore important. In this study, the effectiveness of problem-based learning (PBL) and lecture-based learning in improving the questioning abilities of medical students (N = 104) was assessed by a modified 20-question task. In this task, the participants were asked to identify target pictures by asking questions, the problem-solving process of which resembles that of the diagnosis scenario. Moreover, this task requires no medical knowledge, and therefore allows knowledge-irrelevant questioning abilities to be assessed independently. The results show that PBL students generally ask more efficient questions and use fewer questions to complete the task. This finding suggests that PBL curricula may help improve the questioning strategies of medical students and help them diagnose more efficiently in future diagnosis practice.