In this study, we develop a solution method for solving air express cargo loading problems under stochastic demands. The method is designed by combining a scenario decomposition technique and genetic algorithm. This increases the solution accuracy, thus helping carriers obtain a better container loading plan, which will improve their profitability. Numerical tests are performed to evaluate the performance of the solution method using data for the Asian operations of an international express carrier.