Achieving accurate speed prediction provides the most critical support parameter for high-level energy management of plug-in hybrid electric vehicles. Nowadays, people often drive a vehicle on fixed routes in their daily travels and accurate speed predictions of these routes are possible with random prediction and machine learning, but the prediction accuracy still needs to be improved. The prediction accuracy of traditional prediction algorithms is difficult to further improve after reaching a certain accuracy; problems, such as over fitting, occur in the process of improving prediction accuracy. The combined prediction model proposed in this paper can abandon the transitional dependence on a single prediction. By combining the two prediction algorithms, the fusion of prediction performance is achieved, the limit of the single prediction performance is crossed, and the goal of improving vehicle speed prediction performance is achieved. In this paper, an extraction method suitable for fixed route vehicle speed is designed. The application of Markov and back propagation (BP) neural network in predictions is introduced. Three new combined prediction methods, all named Markov and BP Neural Network (MBNN) combined prediction algorithm, are proposed, which make full use of the advantages of Markov and BP neural network algorithms. Finally, the comparison among the prediction methods has been carried out. The results show that the three MBNN models have improved by about 19%, 28%, and 29% compared with the Markov prediction model, which has better performance in the single prediction models. Overall, the MBNN combined prediction models can improve the prediction accuracy by 25.3% on average, which provides important support for the possible optimization of plug-in hybrid electric vehicle energy consumption.