This article presents a metaheuristic algorithm to solve the pallet-building problem and the loading of these in trucks. This approach is used to solve a real application of a Colombian logistics company. Several practical requirements of goods loading and unloading operations were modeled, such as the boxes’ orientation, weight support limits associated with boxes, pallets and vehicles, and static stability constraints. The optimization algorithm consists of a two-phase approach, the first is responsible for the construction of pallets, and the second considers the optimal location of the pallets into the selected vehicles. Both phases present a search strategy type of GRASP. The proposed methodology was validated through the comparison of the performance of the solutions obtained for deliveries of the logistics company with the solutions obtained using a highly accepted commercial packing tool that uses two different algorithms. The proposed methodology was compared in similar conditions with the previous works that considered the same constraints of the entire problem or at least one of the phases separately. We used the sets of instances published in the literature for each of the previous works. The results allow concluding that the proposed algorithm has a better performance than the most known commercial tool for real cases. The proposed algorithm managed to match most of the test instances and outperformed some previous works that only involve decisions of one of the two problems. As future work, it is proposed to adapt this work to the legal restrictions of the European community.