Problem-solving efficacy is important for students to become effective problem solvers in their profession and for career success. However, the literature indicated that Vietnamese university students are weak in problem-solving efficacy. Despite the elaboration of the importance of problem-solving efficacy to university students in previously stated research, unfortunately, there has not yet been much research into the problem-solving efficacy of Vietnamese university students. Thus, this study was conducted to explore the relationship between academic learning and problem-solving efficacy of Vietnamese university students. This study used a questionnaire survey to gather data. The final survey was conducted with 700 students from five member universities at Vietnam National University of Ho Chi Minh City. The results of this study showed that Vietnamese university students’ problem-solving efficacy was within the range of “average” to “high” response. There existed significant differences of problem-solving efficacy of students among the five universities. In addition, Vietnamese university students’ problem-solving efficacy is significantly influenced by their backgrounds and academic learning.