Mouse pre-implantation development gives rise to the blastocyst, which is made up of at least three distinct cell types: the trophectoderm (TE) that surrounds a cavity, and an inner cell mass (ICM) comprising the primitive endoderm (PE) and epiblast (EPI). However, the underlying mechanisms involved in patterning the cleavage-stage embryo are still unresolved. By analyzing the distribution of the transcription factors Oct4 (Pou5f1), Cdx2 and Nanog at precisely defined stages in pre-implantation development, we were able to identify critical events leading to the divergence of TE, EPI and PE lineages. We found that Oct4 is present in all cells until late blastocyst, gradually disappearing from the TE thereafter. The expression patterns of both Cdx2 and Nanog exhibit two specific phases, culminating in their restriction to TE and EPI, respectively. In the first phase, starting after compaction, blastomeres show highly variable Cdx2 and Nanog protein levels. Importantly, the variability in Nanog levels is independent of position within the morula,whereas Cdx2 variability may originate from asymmetric cell divisions at the 8-cell stage in a non-stereotypic way. Furthermore, there is initially no reciprocal relationship between Cdx2 and Oct4 or between Cdx2 and Nanog protein levels. In the second phase, a definite pattern is established,possibly by a sorting process that accommodates intrinsic and extrinsic cues. Based on these results, we propose a model in which early embryonic mouse patterning includes stochastic processes, consistent with the highly regulative capacity of the embryo. This may represent a feature unique to early mammalian development.