Bottlenecks in population size can reduce fitness and evolutionary potential, yet introduced species often become invasive. This poses a dilemma referred to as the genetic paradox of invasion. Three characteristics must hold true for an introduced population to be considered paradoxical in this sense. First, it must pass through a bottleneck that reduces genetic variation. Second, despite the bottleneck, the introduced population must not succumb to the many problems associated with low genetic variation. Third, it must adapt to the novel environment. Some introduced populations are not paradoxical as they do not combine these conditions. In some cases, an apparent paradox is spurious, as seen in introduced populations with low diversity in neutral markers that maintain high genetic variation in ecologically relevant traits. Even when the genetic paradox is genuine, unique aspects of a species' biology can allow a population to thrive. We propose research directions into remaining paradoxical aspects of invasion genetics.