Hidden Markov Model (HMM) is one of the simple but effective models for DNA sequence modeling, and the first-order HMM has been popularly used in practice. However, due to the non-aftereffect property, a first-order HMM cannot describe the dependencies between adjacent bases. This generally results in the loss of useful statistics in sequences. In this paper, based on the analysis of the specific biological structure for DNA sequences, a second-order HMM for DNA sequence classification is proposed. The new model inherits the advantages of the first-order model, while fully expresses the biological statistics contained in the DNA sequences, which makes the model more meaningful in biology. Based on the new model, a new Bayesian method is proposed for DNA sequence classification, which is experimentally evaluated on the real DNA sequences. The experimental results show that the new method is able to obtain high classification accuracy, as the structure information hidden in bases of DNA sequences can be captured more adequately by the new second-order HMM.