This paper presents ANTBAL, an ant colony optimization algorithm for balancing mixed-model assembly lines. The proposed algorithm accounts for zoning constraints and parallel workstations and aims to minimize the number of operators in the assembly line for a given cycle time. In addition to this goal, ANTBAL looks for solutions that smooth the workload among workstations, which is an important aspect to account for in balancing mixed-model assembly lines. Computational experience shows the superior performance of the proposed algorithm.