Plant invasions can change native communities in complex ways. Restoring invasion-altered habitats starts with invader removal, and imposes significant physical and compositional changes. Restoration facilitates desirable plant community development, but arthropod community responses to removal and the timelines required for native vegetation establishment are difficult to predict. We examined initial effects of Elaeagnus angustifolia (Russian olive) removal on arthropod communities during a long-term experiment evaluating the combined consequences of invasive shrub removal and plant community restoration. We sampled E. angustifolia-invaded areas pre-removal (2010) and post-removal (2013) using sweep netting, and identified arthropods to family level. We found greater variation in the arthropod community composition within removal blocks than within invaded blocks after two years. These shifts resulted from changes in the relative abundance of community members (e.g., Dictynidae (Araneae), Culicidae (Diptera), and Cicadellidae (Hemiptera)), rather than overall richness or diversity. This response is likely due to increased plant diversity in E. angustifolia removal sites but also structural differences in vegetation cover after removal. Removing a dominant structural element like E. angustifolia instantly changes the successional stage of the ecosystem. Thus, restoration managers should consider methods that maintain structural continuity during restoration implementation. Arthropods provide important ecosystem services such as nutrient cycling and pollination and serve as a prey base for higher trophic levels. Thus, understanding how arthropod communities change after plant restoration events is vital to assessing future management decisions to limit ecosystem impacts of invasive plants and their management.