Most of the current applications which use dynamic Bayesian network to model gene regulatory network assume that the time delay between regulators and their targets is one time unit in a time series gene expression dataset. In fact, multiple time units delay is indicated to exist in a gene regulation process. In this paper, we propose using higherorder Markov dynamic Bayesian network(DBN) to model multiple time units delayed gene regulatory network. A two steps heuristic learning framework is designed to learn higher-order Markov DBN from time series gene expression data. We apply the learning framework to a yeast cell cycle gene expression dataset. The predicted gene regulatory network is strongly supported by biological evidence and consistent with the yeast cell cycle phase information.