Abstract Grid partitioning is very important to achieving the load balancing of parallel structured aerodynamics simulations. For the large-scale parallel computing, the greedy partitioning (Greedy) algorithm may degrade the load balancing performance and even be infeasible for complex grids. In this paper, we propose two structured partitioning algorithms, the multi-dimensional greedy (MG) algorithm and the grid-first multi-dimensional (GFM) algorithm, to mitigate the issue. The new methods satisfy the specific requirement of stencil width in high-order aerodynamics applications. Moreover, the partitioning rules we presented are also satisfied in the new methods for better connectivity among sub-blocks. We validate and evaluate our methods using three realistic and complex three-dimensional structured configurations. Our experimental results with our in-house high-order aerodynamics software show that MG can achieve a speedup of 1.27x, 1.38x, and 1.21x for the three complex configurations, compared to Greedy, while the number for GFM is 1.36x, 1.24x, and 1.22, respectively.