Flight delay is a nondeterministic problem. Modeling and estimating flight delay is very important in the flight delay research. It is also the precondition to calculate delay propagation. A new Bayesian network structure learning algorithm, named target-fixed stochastic-ordered K2(TSK2), has been proposed in this paper. After using this new algorithm to build the Bayesian network of flight delay, TSK2 has been proved to be suitable to modeling flight delay, and the trained models can use to estimate the delay of arrival and departure flights reliably.