Self-efficacy and critical thinking represent two vital components for university graduates in the 21st century learning. However, several studies reported that these two important outcome predictors were unsatisfactory. This study aimed at investigating the effects of problem-based learning (PBL) on pre-service teachers' self-efficacy and critical thinking. A quasi-experimental nonequivalent pretest-posttest control group design was utilized. A total of 44 pre-service elementary school teachers (aged 19-22) at a private university in Indonesia were assigned as experimental (n = 22) and control (n = 22) groups. The experimental group learning received PBL, while the control group learning with traditional college instruction. The Self-Efficacy Scale (SES) and the Critical Thinking Questionnaire (CTQ) were administered before and after the intervention in both groups. Independent and paired samples t-tests were employed to analyze the pretests and posttests data. The results indicated that PBL was more effective in increasing self-efficacy and critical thinking of pre-service elementary teachers than traditional teaching. It is suggested that PBL should be used more frequently in science learning to further enhance students' self-efficacy and critical thinking skills in higher education.