A specialized subset of invasive embryonic cytotrophoblast cells gains access to maternal uterine arteries early in the gestation of higher primates. These cells continue to migrate extensively within the lumina of spiral arteries, converting them to the highly modified uteroplacental arteries of pregnancy. Although trophoblast cell-mediated modifications are considered critical to the progress of normal pregnancy, few studies have addressed the cellular interactions between maternal arteries and embryonic cells in situ. Macaque placentas and endometrial tissues were collected from 12 animals from day 14 of gestation (blastocyst implantation begins on day 9) to day 49. Standard indirect immunoperoxidase methods were used to identify matrix metalloproteinases (MMP-1, MMP-3, MMP-9), cathepsin B, cathepsin D, platelet-endothelial cell adhesion molecule, cytokeratins, smooth muscle actin, CD68, and factor VIII-related antigen. Cytotrophoblast cells were located deep within spiral arteries in each of the specimens examined. In some examples tightly packed clusters of cytotrophoblast occluded the lumina of invaded arteries. Initial penetration of arterial tunica intima was revealed by discontinuities in the staining pattern for factor VIII and cytotrophoblast intrusion was indicated by cytokeratin staining of the trophoblast cells. Continued cytotrophoblast intrusion into the tunica media was apparent by gaps in the smooth muscle. MMP-1, MMP-3, and MMP-9 were localized within intraluminal and intramural cytotrophoblast. By contrast, neither cathepsin B nor cathepsin D were present, although both were seen in uterine macrophages and stromal cells. Upon reaching the surrounding uterine stroma the cytotrophoblast cells ceased migration. As cytotrophoblast accumulated in the arterial wall the vascular lumen expanded. Evidence of cell death was rarely encountered in associated maternal or embryonic tissues. We conclude that intra-arterial cytotrophoblast cells express several proteinases with substrate specificities sufficient to permit independent remodeling of the extracellular matrix comprising uterine artery walls. The remodeling of the arteries, which involves extensive displacement of maternal endothelium and smooth muscle, in addition to degradation and synthesis of extracellular matrix, is accomplished with little evidence of cell death or loss of the integrity of the arteries. This process provides an interesting example of cooperation between different types of interacting tissues from genetically distinct individuals.