Primitive erythropoiesis defines the onset of hematopoiesis in the yolk sac of the early embryo and is initiated by the emergence of progenitors assayed as colony-forming cells (EryP-CFCs). EryP-CFCs are detected for only a narrow window during embryonic development, suggesting that both their initiation and termination are tightly controlled. Using the embryonic stem differentiation system to model primitive erythropoiesis, we found that miR-126 regulates the termination of EryP-CFC development. Analyses of miR-126 null embryos revealed that this miR also regulates EryP-CFCs in vivo. We identified vascular cell adhesion molecule-1 (Vcam-1) expressed by a mesenchymal cell population as a relevant target of miR-126. Interaction of EryP-CFCs with Vcam-1 accelerated their maturation to ßh1-globin + and Ter119 + cells through a Src family kinase. These findings uncover a cell nonautonomous regulatory pathway for primitive erythropoiesis that may provide insight into the mechanism(s) controlling the developmental switch from primitive to definitive hematopoiesis.