Despite the increasing emphasis on computational literacy in higher education, we observed that many undergraduate students particularly in developing contexts struggle to master fundamental programming skills and develop critical thinking. Conventional instructional approaches often lack interactivity and personalized scaffolding, which are essential for teaching abstract programming concepts. In response to this challenge, we examined the effect of artificial intelligence (AI)-assisted problem-based learning (PBL) on students' programming skills, critical thinking, and problem-solving abilities in Java programming. Grounded in a quasi-experimental pre-test post-test control group design, we involved 62 s-year computer science education students from two public universities in Nigeria. Participants were assigned to either an experimental group that used Google Gemini (AI) within a PBL framework or a control group exposed to PBL adopting instructional videos. We employed four validated instruments to measure computer programming skills (CPSAR), critical thinking (CTS), problem-solving (PSS), and academic ability. Using multivariate analysis of covariance (MANCOVA), we analyzed group differences while controlling for pre-test scores and tested moderation effects of academic ability and age group. Our results revealed a statistically significant improvement in programming skills among students in the AI-assisted group, with a large effect size. Critical thinking and problem-solving skill outcomes did not differ significantly between the groups. We also found a significant interaction between the teaching strategy and academic ability, indicating that high-ability students benefited more from AI integration into computer programming instruction. This study provides original insights into AI-enhanced pedagogy and has practical implications for improving programming instruction, particularly in resource-limited educational environments.