The Colombian Paso breed CCC is the main horse breed in the country, with more than a half million animals, and includes three different subpopulations defined by gaits. It descended from some horse populations which Columbus brought to the Americas in the XVI century. These populations were selected by local breeders for different farming activities considering the variety of Colombian topographic landscapes; therefore, for centuries those breeders were looking for animals with particular movements that were able to correctly perform on those places. We tested the hypothesis whether or not there is a genetic structure based on gait selection. This approach was made through an exhaustive analysis of genetic information including 14–16 autosomal microsatellite markers (140,000 genotypes), X chromosome microsatellites (1000 genotypes), mitochondrial d-loop sequences (200 animals), genealogical information (226,000 records approx.), and phenotypic data (morphometric and gait information). All data were analyzed by using statistical tools, population genetics approaches and phylogenetic reconstruction. The analyses show a single breed with a genetic structure based on the selection of different gaits through the history of this population. That is supported by significant phenotypic differences among the populations defined by gaits. Genetic differences have been increasing in the last 20 yr, so it is possible that if artificial selection provides the reproductive barriers among gaits, it could be possible in the near future that the CCC breed would become two or more different breeds. Finally, the phylogenetic and genealogical reconstructions show a single common origin of these subpopulation which demonstrates a single substructured breed.