Time-cost trade-off analysis is addressed as an important aspect of any construction project planning and control. Nonexistence of a unique solution makes the time-cost trade-off problems very difficult to tackle. As a combinatorial optimization problem one may apply heuristics or mathematical programming techniques to solve time-cost trade-off problems. In this paper, a new multicolony ant algorithm is developed and used to solve the time-cost multiobjective optimization problem. Pareto archiving together with innovative solution exchange strategy are introduced which are highly efficient in developing the Pareto front and set of nondominated solutions in a time-cost optimization problem. An 18-activity time-cost problem is used to evaluate the performance of the proposed algorithm. Results show that the proposed algorithm outperforms the well-known weighted method to develop the nondominated solutions in a combinatorial optimization problem. The paper is more relevant to researchers who are interested in developing new quantitative methods and/or algorithms for managing construction projects.