In a project, the duration of every activity is uncertain because of weather, availability of machines, human resources, and unexpected situations, and the cost is influenced by the duration. For modeling the uncertain durations, a multi-state project network (MPN) is proposed. To understand the performance of an MPN, project reliability is calculated and defined as the probability that a project can be completed within time and budget constraints. All feasible project state vectors are contained in upper and lower boundary points. The previous literature only calculated an estimated project reliability. To obtain the exact project reliability, a decomposition approach is developed to obtain subsets of feasible project state vectors. Each subset is firstly formed in terms of one upper boundary point and all lower boundary points. Each subset is further simplified to reduce the number of lower boundary points for computational efficiency. An algorithm with the decomposition approach is subsequently proposed to evaluate the exact project reliability. A real project of new manufacturing lines is demonstrated with several combinations of time and budget constraints to show the effectiveness of the proposed algorithm, and project managers can make decisions based on project reliability.