If we take the archaeological record at face value, the colonization of unglaciated North America appears to have been very rapid. The highly consistent dating of Clovis archaeological sites (11,500-10,800 B.P.) suggests that this continent was populated within a matter of centuries. To explain the spatial and temporal scales of this phenomenon, it is necessary to invoke both high mobility and high fertility rates during the initial colonization process. However, it is widely believed that it is maladaptive for mobile foragers to have large numbers of offspring due to the costs of transporting those children. Thus, the archaeological record presents us with a paradox. Using a mathematical model that estimates the costs of raising children for mobile hunter-gatherers, this paper asks the question-is high mobility compatible with high fertility? It is concluded that high mobility, if defined as the frequent movement of residential base camps, is quite compatible with high fertility, and that early Paleoindians could indeed have been characterized by high reproductive rates. Therefore, it is quite possible that the Americas were populated very rapidly by highly mobile hunter-gatherers.