The proposed modeling approach for nanocrystalline materials is an extension of the local phase mixture model introduced by Kim et al (2000 Acta Mater. 48 493-504). Local models cannot account for any non-uniformities or strain patterns, i.e. such models describe the behavior correctly only as long as it is homogeneous. In order to capture heterogeneities, the phase mixture model is augmented with gradient terms of higher order, namely second and fourth order. Different deformation mechanisms are assumed to operate in grain interior and grain boundaries concurrently. The deformation mechanism in grain boundaries is associated with diffusional mass transport along the boundaries, while in the grain interior dislocation glide as well as diffusion controlled mechanisms are considered. In particular, the mechanical response of nanostructured polycrystals is investigated. The model is capable of correctly predicting the transition of flow stress from Hall-Petch behavior in conventional grain size range to an inverse Hall-Petch relation in the nanocrystalline grain size range. The consideration of second- and fourth-order strain gradients allows non-uniformities within the strain field to represent strain patterns in combination with a regularization effect. Details of the numerical implementation are provided.