Incorporating scientific fundamentals via engineering through a design-based methodology has proven to be highly effective for STEM education. Engineering design can be instantiated for learning as they involve mental and physical stimulation and develop practical skills especially in solving problems. Lego bricks, as a set of toys based on design technique, are in line with the cognitive characteristics of students and provide a good game-based learning tool for engineering education. Many studies have incorporated Lego to investigate students' scientific attitudes, science inquiry skills, and problem-solving strategies, yet few address the effects of engineering design-based learning on pupils' problem-solving abilities. Therefore, this paper conducted an experiment and included control group to examine how fourth-grade students' science performance and problem-solving abilities change over the engineering design-based science learning by using Lego bricks. Results indicate that: (1) pupils' science performance significantly improved on both the control and the experimental groups, (2) pupils' gains of problem-solving ability in the experimental group were significantly improved, and (3) the males made a significant progress in problem-solving ability than the females in the experimental group. The key findings, possible reasons behind them, and potential benefits in the context of learning are also discussed.