Invasive species have devastating consequences for human health, food security, and the environment. Many invasive species adapt to new ecological niches following invasion, but little is known about the early steps of adaptation. Here we examine population genomics of a recently introduced drosophilid in North America, the African Fig Fly, Zaprionus indianus. This species is likely intolerant of subfreezing temperatures and recolonizes temperate environments yearly. We generated a new chromosome-level genome assembly for Z. indianus. Using resequencing of over 200 North American individuals collected over four years in temperate Virginia, plus a single collection from subtropical Florida, we tested for signatures of recolonization, population structure, and adaptation within invasive populations. We show founding populations are sometimes small and contain close genetic relatives, yet temporal population structure and differentiation of populations is mostly absent across recurrent recolonization events. Although we find limited signals of genome-wide spatial or temporal population structure, we identify haplotypes on the X chromosome that are repeatedly differentiated between Virginia and Florida populations. These haplotypes show signatures of natural selection and are not found in African populations. We also find evidence for several large structural polymorphisms segregating within North America populations and show X chromosome evolution in invasive populations is strikingly different from the autosomes. These results show that despite limited population structure, populations may rapidly evolve genetic differences early in an invasion. Further uncovering how these genomic regions influence invasive potential and success in new environments will advance our understanding of how organisms evolve in changing environments.