Uterine spiral arteriole (SA) remodeling in early pregnancy involves a coordinated series of events including decidual immune cell recruitment, vascular cell disruption and loss, and colonization by placental-derived extravillous trophoblast (EVT). During this process, decidual SA are converted from narrow, muscular vessels into dilated channels lacking vasomotor control. We hypothesized that this extensive alteration in SA architecture must require significant reorganization and/or breakdown of the vascular extracellular matrix (ECM). First trimester decidua basalis (30 specimens) was immunostained to identify spiral arterioles undergoing trophoblast-independent and -dependent phases of remodeling. Serial sections were then immunostained for a panel of ECM markers, to examine changes in vascular ECM during the remodeling process. The initial stages of SA remodeling were characterized by loss of laminin, elastin, fibrillin, collagen types III, IV and VI from the basement membrane, vascular media and/or adventitia, and surrounding decidual stromal cells. Loss of ECM correlated with disruption and disorganization of vascular smooth muscle cells, and the majority of changes occurred prior to extensive colonization of the vessel wall by EVT. The final stages of SA remodeling, characterized by the arrival of EVT, were associated with the increased mural deposition of fibronectin and fibrinoid. This study provides the first detailed analysis of the spatial and temporal loss of ECM from the walls of remodeling decidual SA in early pregnancy.