Recent studies of the Uruguayan population revealed different amounts of Amerindian and African genetic contributions. Our previous analysis of Afro-Uruguayans from the capital city of the Department of Cerro Largo showed a high proportion of African genes, and the effects of directional mating involving Amerindian women. In this paper, we extended the analysis to a sample of more than 100 individuals representing a random sample of the population of the whole Department. Based on 18 autosomal markers and one X-linked marker, we estimated 82% European, 8% Amerindian, and 10% African contributions to their ancestry, while from seven mitochondrial DNA site-specific polymorphic markers and sequences of hypervariable segment I, we determined 49% European, 30% Amerindian, and 21% African maternal contributions. Directional matings between Amerindian women and European men were detected, but differences involving Africans were not significant. Data about the specific origins of maternal lineages were also provided, and placed in a historical context.