Despite intensive research efforts that have been devoted to discrete time-cost optimization of construction projects, the current methods have very limited capabilities for solving the problem for real-life-sized projects. This study presents a new activity uncrashing heuristic with noncritical activity rescheduling method to narrow the gap between the research and practice for time-cost optimization. The uncrashing heuristic searches for new solutions by uncrashing the critical activities with the highest cost-slope. This novel feature of the proposed heuristic enables identification and elimination of the dominated solutions during the search procedure. Hence, the heuristic can determine new high-quality solutions based on the nondominated solutions. Furthermore, the proposed noncritical activity rescheduling method of the heuristic decreases the amount of scheduling calculations, and high-quality solutions are achieved within a short CPU time. Results of the computational experiments reveal that the new heuristic outperforms state-of-the-art methods significantly for large-scale single-objective cost minimization and Pareto front optimization problems. Hence, the primary contribution of the paper is a new heuristic method that can successfully achieve high-quality solutions for large-scale discrete time-cost optimization problems.