The conventional Project-Based Learning (PBL) pedagogy consists of five stages: Preparation, Implementation, Presentation, Evaluation, and Revision. When applied to an application domain, PBL lacks in two features, namely creative thinking and design process. This work tries to bridge the gap by proposing an innovative PBL (iPBL), which integrates two frameworks, namely creative learning and Conceive-Design-Implement-Operate (CDIO). Creative learning helps problem solving to be more innovative, while CDIO associates a proven design process with problem solving so that results are more convergent. iPBL consists of 7 stages including Preparation (P), Conception (C), Design (D), Implementation (I), Operation (O), Evaluation (E), and Revision (R). iPBL has been implemented on an instructional platform for a class of 85 junior students taking the capstone course in our computer science department. There were 46 experiment groups and 39 control groups. For creative thinking, brainstorming and 6-3-5 were applied in the conception phase, SCAMPER in the design phase, and TRIZ in the implementation phase. The application of iPBL to a capstone course demonstrated not only significantly increased creativity, but also a more systematic record and analysis of all creativity tasks.