Dams and their impoundments disrupt river habitat connectivity to the detriment of migratory fishes. Removal of dams improves riverine connectivity and lotic habitat, which benefits not only these fishes but also resident fluvial specialist species. Restoration efforts on the Penobscot River, Maine, are among the largest recently completed in the United States and include the removal of the two lowermost dams and improvements to fish passage at several remaining barriers. We assessed fish assemblages in the main‐stem river and several major tributaries before (2010–2012) and after (2014–2016) dam removal using boat electrofishing surveys and a stratified random sampling design. In total, we sampled 303 km of shoreline and captured 107,335 individual fish representing 39 species. Similarity indices and rarefaction curves indicated that significant changes in fish assemblage composition occurred in reaches that underwent both habitat and connectivity changes (i.e., directly above removed dams). The newly connected reaches became more similar in fish assemblage composition, as demonstrated by an average increase of 31% in similarity scores. The changes in similarity score in these reaches were driven by increasing access for anadromous fishes and decreasing abundances of slow‐water specialist species. For example, we observed a marked reduction in lacustrine species in former impoundments. These assemblage shifts were further illustrated by nonmetric multidimensional scaling in which sites directly above former dams exhibited the largest ordinal shifts immediately following dam removal. We also found all anadromous species in greatest abundance below the lowermost dam during each respective sampling period, though we did find some anadromous species above the lowermost dam during postremoval sampling. Our results demonstrate the potential for large dam removal projects to restore both fluvial and anadromous fish assemblages.