The aim of this study was to investigate population structure and genetic trends based on pedigree and performance records of five indigenous African beef cattle breeds (Afrikaner, Boran, Drakensberger, Nguni and Tuli) in South Africa. Pedigree completeness over six generations was higher than 88.5% in the first generation for all breeds, except for the Boran, which was introduced to South Africa only recently. The average generation interval ranged between 6.0 and 6.4 years. The rates of inbreeding per generation varied between 0.18% and 0.52%, while the effective population sizes ranged between 89 and 364. This is sufficient to maintain the genetic diversity within all of these populations. Inbreeding and effective population size for the Boran breed could not be accurately estimated, because it was introduced into South Africa only recently. Estimated breeding values for growth traits and scrotal circumference were also included for analyses to determine genetic trends of the same five breeds. Breeding values were regressed on birth year from 1986 to 2012. Genetic progress has been made in weaning and post weaning weights for all the breeds. This study has confirmed the benefits of having sufficient pedigree and performance data available for genetic evaluations and application in selection for genetic improvement.