Design and optimization of trawl-doors are key factors in minimizing the fuel consumption of fishing vessels. This paper discusses optimization of the trawl-door shapes using high-fidelity 3D computational fluid dynamic (CFD) models. The accurate 3D CFD models are computationally expensive and, therefore, the direct use of traditional optimization algorithms, which often require a large number of evaluations, may be prohibitive. The design approach presented here is a variation of sequential approximate optimization exploiting low-order local response surface models of the expensive 3D CFD simulations. The algorithm is applied to the design of modern and airfoil-shaped trawl-doors.