Date palm (Phoenix dactylifera L.) is a major tree crop in arid regions of the Middle East and North Africa, having an important impact on the economy of many countries in these regions. Date palms are traditionally propagated through offshoots. The development of propagation methods through tissue culture resulted in massive expansion of date palm plantations. While most trees generated from tissue culture are normal and true-to-type, several typical abnormal phenotypes are detected. The present study applies amplification fragment length polymorphism (AFLP) analysis to characterize the genetic variation of two elite date cultivars, `Barhee' and `Medjool', as well as male clones, propagated from offshoots and through tissue culture. The two cultivars have very distinct AFLP band patterns. Most offshoots, as well as the tissue culture-propagated plants, have very similar band patterns, demonstrating a low level of genetic variation. However, a significant level of genetic variation was detected among `Medjool' plants generated from tissue culture. Several phenotypically abnormal trees were characterized by unique and different AFLP band patterns. The male clones are characterized by a high level of polymorphic bands. Genetic variation was also detected between various tissues of variegated `Medjool' trees propagated from tissue culture. The significance of these results, regarding the mechanism of the phenomenon and its relevance to agricultural practice, is discussed.