This paper proposes a new algorithm, called Edge-based Texture Driven Shape Model (E-TDSM), for nonfrontal face alignment task. First, the texture is defined as the un-warped edge image contained in the shape rectangle; then,a Bayesian network is constructed to describe the relationship between the shape and texture models; finally, ExpectationMaximization (EM) approach is utilized to infer the optimal texture and position parameters from the observed shape and texture information. Compared with the traditional shape localization algorithms, E-TDSM has the following advantages:1) the un-warped edge-based texture can better predict the shape and is more robust to the illumination and expression variation than the conventional warped gray-level based texture; 2) the presented Bayesian network indicates the logic structure of the face alignment task; and 3) the mutually enhanced shape and texture observations are integrated to infer the optimal parameters of the proposed Bayesian network using EM approach. The extensive experiments on non-frontal face alignment task demonstrate the effectiveness and robustness of the proposed E-TDSM algorithm.