Sedgeunkedunk Stream, a third-order tributary to the Penobscot River, Maine, historically supported several anadromous fishes, including the Atlantic Salmon Salmo salar, AlewifeAlosa pseudoharengus, and Sea Lamprey Petromyzon marinus. However, two small dams constructed in the 1800s reduced or eliminated spawning runs entirely. In 2009, efforts to restore marine–freshwater connectivity in the system culminated with removal of the lowermost dam, thus providing access to an additional 4.6 km of lotic habitat. Because Sea Lampreys utilized accessible habitat prior to dam removal, they were chosen as a focal species with which to quantify recolonization. During spawning runs of 2008–2011 (before and after dam removal), individuals were marked with PIT tags and their activity was tracked with daily recapture surveys. Open-population mark–recapture models indicated a fourfold increase in the annual abundance of spawning-phase Sea Lampreys, with estimates rising from 59±4 () before dam removal (2008) to 223±18 and 242±16 after dam removal (2010 and 2011, respectively). Accompanying the marked increase in annual abundance was a greater than fourfold increase in nesting sites: the number of nests increased from 31 in 2008 to 128 and 131 in 2010 and 2011, respectively. During the initial recolonization event (i.e., in 2010), Sea Lampreys took 6 d to move past the former dam site and 9 d to expand into the furthest upstream reaches. Conversely, during the 2011 spawning run, Sea Lampreys took only 3 d to penetrate into the upstream reaches, thus suggesting a potential positive feedback in which larval recruitment into the system may have attracted adult spawners via conspecific pheromone cues. Although more research is needed to verify the migratory pheromone hypothesis, our study clearly demonstrates that small-stream dam removal in coastal river systems has the potential to enhance recovery of declining anadromous fish populations.