Successful remodeling of the uterine spiral arteries is essential for a complication-free pregnancy and is best described in terms of its morphologic features. The molecular mediators and cellular sources of spiral artery remodeling are not known, although a role for uterine leukocytes has been proposed. Immunohistochemical assessment of placental bed biopsies demonstrated uterine NK cells, macrophages, and T lymphocytes in the wall and adventitia of spiral arteries at different stages of remodeling, regardless of the presence of extravillous trophoblast cells. Leukocytes were more prevalent in vessel adventitia than wall, and macrophages were the most abundant leukocyte population. Macrophages, separated from early pregnancy decidua, did not alter extravillous trophoblast cells invasion or vascular smooth muscle cell organization or differentiation status but did induce extracellular matrix breakdown (reduced immunostaining of laminin, P = 0.05; fibronectin, P = 0.02) and were able to phagocytose apoptotic vascular smooth muscle cells. Decidual macrophages were shown to secrete a wide range of cytokines (IL-1β, -2, -4, -5, -6, -8, -10, and -13 and TNF-α), proteases (matrix metalloproteinase-1, -2, -7, -9, and -10), and angiogenic growth factors (angiogenin, keratinocyte growth factor, fibroblast growth factor B, vascular endothelial growth factor A, and angiopoietin-1 and -2). We conclude that spiral artery remodeling involves the coordinated activity of a range of cell types, including extravillous trophoblast cells, decidual uterine NK cells, and macrophages in a carefully, spatiotemporally regulated manner.