Goal: Difficult tracheal intubation is a major cause of anesthesia related injuries with potential life threatening complications. Detection and anticipation of difficult airway in the preoperative period is thus crucial for the patients’ safety. We propose an automatic face analysis approach to detect morphological traits related to difficult intubation and improve its prediction. Methods: For this purpose, we have collected a database of 970 patients including photos, videos and ground truth data. Specific statistical face models have been learned using the faces in our database providing an automated parametrization of the facial morphology. The most discriminative morphological features are selected through the importance ranking provided by the random forest algorithm. The random forest approach has also been used to train a classifier on these selected features. We compare a threshold tuning method based on class prior with two methods which learn an optimal threshold on a training set for tackling the inherent imbalanced nature of the database. Results: Our fully-automated method achieves an AUC of 81.0% in a simplified experimental setup where only easy and difficult patients are considered. A further validation on the entire database has proven that our method is applicable for real-world difficult intubation prediction, with AUC = 77.9%. Conclusion: The system performance is in line with the state-of-the-art medical diagnosis, based on ratings provided by trained anesthesiologists, whose assessment is guided by an extensive set of criteria. Significance: We present the first completely automatic and non-invasive difficult intubation detection system that is suitable for use in clinical settings.