Ecotypic variation among populations may become associated with widespread genomic differentiation, but theory predicts that this should happen only under particular conditions of gene flow, selection and population size. In closely related species, we might expect the strength of host-associated genomic differentiation (HAD) to be correlated with the degree of phenotypic differentiation in host-adaptive traits. Using microsatellite and Amplified Fragment Length Polymorphism (AFLP) markers, and controlling for isolation by distance between populations, we sought HAD in two congeneric species of butterflies with different degrees of host plant specialization. Prior work on Euphydryas editha had shown strong interpopulation differentiation in host-adapted traits, resulting in incipient reproductive isolation among host-associated ecotypes. We show here that Euphydryas aurinia had much weaker host-associated phenotypic differentiation. Contrary to our expectations, we detected HAD in Euphydryas aurinia, but not in E. editha. Even within an E. aurinia population that fed on both hosts, we found weak but significant sympatric HAD that persisted in samples taken 9 years apart. The finding of significantly stronger HAD in the system with less phenotypic differentiation may seem paradoxical. Our findings can be explained by multiple factors, ranging from differences in dispersal or effective population size, to spatial variation in genomic or phenotypic traits and to structure induced by past histories of host-adapted populations. Other infrequently measured factors, such as differences in recombination rates, may also play a role. Our result adds to recent work as a further caution against assumptions of simple relationships between genomic and adaptive phenotypic differentiation.