This paper outlines the need for and the requirements of trip prediction to optimally derive the charging behavior of plug-in electric vehicles. The information required for trip prediction by a charging-service provider is shown, and a novel trip prediction model is proposed. The proposed model is a semi-Markov model that predicts the next arrival location and the waiting time at the current location. Combining this with a prediction of the energy need and the duration of the trip to the predicted location provides a basis for determining the charging behavior. The proposed prediction model is compared with a naive predictor that uses yesterday's trips to predict today's trips. It is shown that the proposed model predicts the next location with 84% accuracy. © 2012 IEEE.