Sickle cell anemia is a genetic disease with high prevalence in people of African descent. There are five typical haplotypes associated with this disease and the haplotypes associated with the beta-globin gene cluster have been used to establish the origin of African-descendant people in America. In this work, we determined the frequency and the origin of haplotypes associated with hemoglobin S in a sample of individuals with sickle cell anemia (HbSS) and sickle cell hemoglobin trait (HbAS) in coastal regions of Colombia. Blood samples from 71 HbAS and 79 HbSS individuals were obtained. Haplotypes were determined based on the presence of variable restriction sites within the β-globin gene cluster. On the Pacific coast of Colombia the most frequent haplotype was Benin, while on the Atlantic coast Bantu was marginally higher than Benin. Eight atypical haplotypes were observed on both coasts, being more diverse in the Atlantic than in the Pacific region. These results suggest a differential settlement of the coasts, dependent on where slaves were brought from, either from the Gulf of Guinea or from Angola, where the haplotype distributions are similar. Atypical haplotypes probably originated from point mutations that lost or gained a restriction site and/or by recombination events.