Human action recognition based on the depth maps is an important yet challenging task. In this paper, a new framework based on the 3D motion trail model (3DMTM) and Pyramid Histograms of Oriented Gradient (PHOG) is proposed to recognize human actions from sequences of depth maps. Specifically, a discriminative descriptor called 3DMTM-PHOG is proposed for depth-based human action recognition. The 3DMTM is generated through the entire depth video sequence to encode additional motion information from three projected orthogonal planes. By adding pyramid representation, Histograms of Oriented Gradient (HOG) descriptor is extended to PHOG which can well characterize local shapes at different spatial grid sizes for action recognition. PHOG is then computed from the 3DMTM as the 3DMTM-PHOG descriptor for the representation of an action. The proposed approach based on 3DMTM-PHOG descriptor is evaluated on MSR Action3D dataset captured by depth cameras. Experimental results show that the proposed approach outperforms the state-of-the-art methods and demonstrate the effectiveness and robustness of the proposed 3DMTM-PHOG descriptor.