In many countries, Mycobacterium tuberculosis isolates are routinely subjected to variable-number tandem-repeat (VNTR) typing to investigate M. tuberculosis transmission. Unexpectedly, cross-border clusters were identified among African refugees in the Netherlands and Denmark, although transmission in those countries was unlikely. Whole-genome sequencing (WGS) was applied to analyze transmission in depth and to assess the precision of VNTR typing. WGS was applied to 40 M. tuberculosis isolates from refugees in the Netherlands and Denmark (most of whom were from the Horn of Africa) that shared the exact same VNTR profile. Cluster investigations were undertaken to identify in-country epidemiological links. Combining WGS results for the isolates (all members of the central Asian strain [CAS]/Delhi genotype), from both European countries, an average genetic distance of 80 single-nucleotide polymorphisms (SNPs) (maximum, 153 SNPs) was observed. The few pairs of isolates with confirmed epidemiological links, except for one pair, had a maximum distance of 12 SNPs. WGS divided this refugee cluster into several subclusters of patients from the same country of origin. Although the M. tuberculosis cases, mainly originating from African countries, shared the exact same VNTR profile, most were clearly distinguished by WGS. The average genetic distance in this specific VNTR cluster was 2 times greater than that in other VNTR clusters. Thus, identical VNTR profiles did not represent recent direct M. tuberculosis transmission for this group of patients. It appears that either these strains from Africa are extremely conserved genetically or there is ongoing transmission of this genotype among refugees on their long migration routes from Africa to Europe.