Many real-world problems exhibit phenomena which are best represented as complex networks with dynamic structures (e.g., human communication networks). Network motifs have been shown effective for characterizing the structural properties of such complex networks. Nevertheless, related motif models typically do not consider stochastic structural and sequential variations, hinting their limitations on dynamic network analysis. In this paper, we consider networks with time-stamped edges and model their local structural and temporal variations using a mixture of Markov chains for stochastic temporal network motif detection. The optimal number of motifs is automatically estimated in a Bayesian framework. We evaluated the proposed method using synthetic networks and found to be robust against noise compared to the deterministic approach. Also, we applied it to a mobile phone usage data set to demonstrate how the human communication patterns embedded in the data set can be detected. In addition, we make use of a hidden Markov model with different distributions for the mixing proportions of the motifs defining its states, and demonstrated how the evolution of the communication patterns can also be identified.