Population genetic analysis of invasive populations can provide valuable insights into the source of introductions, pathways for expansion, and their demographic histories. Flathead catfish (Pylodictis olivaris) are a prolific invasive species with high fecundity, long-distance dispersal, and piscivorous feeding habits that can lead to declines in native fish populations. In this study, we analyse the genetics of invasive P. olivaris in the Mid-Atlantic region to assess their connectivity and attempt to reconstruct the history of introduced populations. Based on an assessment across 13 microsatellite loci, P. olivaris from the Susquehanna River system (N = 537), Schuylkill River (N = 33), and Delaware River (N = 1) have low genetic diversity (global H_obs = 0.504), although we detected no evidence of substantial inbreeding (F_IS = −0.083 to 0.022). P. olivaris from these different river systems were genetically distinct, suggesting separate introductions. However, population structure was much weaker within each river system and exhibited a pattern of high connectivity, with some evidence of isolation by distance. P. olivaris from the Susquehanna and Schuylkill rivers showed evidence for recent genetic bottlenecks, and demographic models were consistent with historical records, which suggest that populations were established by recent founder events consisting of a small number of individuals. Our results show the risk posed by small introductions of P. olivaris, which can spread widely once a population is established, and highlight the importance of prevention and sensitive early detection methods to prevent the spread of P. olivaris in the future.