Summary: This paper concerns the two-stage transportation problem with fixed charges associated to the routes and proposes an efficient multi-start Iterated Local Search (ILS) procedure for the total distribution costs minimization. Our heuristic approach constructs an initial solution, uses a local search procedure to increase the exploration, a perturbation mechanism and a neighborhood operator in order to diversify the search. Computational experiments were performed on two sets of instances: one that consists of 20 benchmark instances available in the literature and a second one that contains 10 new randomly generated larger instances. The achieved computational results prove that our proposed solution approach is highly competitive in comparison with the existing approaches from the literature.