Taxi-out time prediction is an effective method for improving airport surface operational efficiency, and it is important in surface traffic management and air traffic management. The taxi-out process is divided into two phases according to the flight departure process and the characteristics of taxi-out time prediction problem. Two phases are the flight taxiing to the runway queue without any obstacles and the taxi-out delay in the queue. After analyzing the influence of departure and arrival flights on the taxi-out time, a measure index of surface traffic and an unimpeded taxi-out time calculation model is proposed. Runway service process is modeled as M/G/1/∞ random service system, and a queue time prediction model is established based on queuing theory. Finally, the predicted average taxi-out time with 15 min intervals in a day of individual flight is used to verify the accuracy of model at Beijing Capital International Airport. Moreover, a comparison with the result of calculation model of Beijing Capital International Airport shows that the proposed model performs significant improvement in prediction accuracy.