Crenate broomrape (Orobanche crenata Forsk.) is a serious long-standing parasitic weed problem in Algeria, mainly affecting legumes but also vegetable crops. Unresolved questions for parasitic weeds revolve around the extent to which these plants undergo local adaptation, especially with respect to host specialization, which would be expected to be a strong selective factor for obligate parasitic plants. In the present study, the Genotyping-By-Sequencing (GBS) approach was used to analyze genetic diversity and population structure of 10 Algerian O. crenata populations with different geographical origins and host species (faba bean, pea, chickpea, carrot and tomato). In total, 8,004 high-quality single-nucleotide polymorphisms were obtained and used across the study. Genetic diversity and relationships of 95 individuals from 10 populations were studied using model-based ancestry analysis, principal components analysis, discriminant analysis of principal components, and phylogeny approaches. The genetic differentiation (FST) between pairs of populations was lower between adjacent populations and higher between geographically separated ones, but no support was found for isolation by distance. Further analyses identified four genetic clusters and revealed evidence of structuring among populations and hosts with more evident structuring among hosts than strictly along a geographic gradient. In the most striking example, O. crenata growing on pea had a distinct SNP profile from those growing on faba bean or other crops. These results illustrate the potential of GBS to reveal the dynamics of parasitic weed dispersal and adaptation.