Banana plantation has been introduced recently to a temperate zone in the southeastern parts of Saudi Arabia (Fifa, Dhamadh, and Beesh, located in Jazan province). The introduced banana cultivars were of a clear origin without a recorded genetic background. In the current study, the genetic variability and structure of five common banana cultivars (i.e., Red, America, Indian, French, and Baladi) were analyzed using the fluorescently labeled AFLP technique. Nine different primer pairs combinations yielded 1468 loci with 88.96% polymorphism. Among all locations, high expected heterozygosity under the Hardy–Weinberg assumption was found (0.249 ± 0.003), where Dhamadh was the highest, followed by Fifa and Beesh, respectively. Based on the PCoA and Structure analysis, the samples were not clustered by location but in pairs in accordance with the cultivar’s names. However, the Red banana cultivar was found to be a hybrid between the American and Indian cultivars. Based on ΦST, 162 molecular markers (i.e., loci under selection) were detected among cultivars. Identifying those loci using NGS techniques can reveal the genetic bases and molecular mechanisms involved in the domestication and selection indicators among banana cultivars.