Although the process of species formation is notoriously idiosyncratic, the observation of pervasive patterns of reproductive isolation across species pairs suggests that generalities, or “rules”, underlie species formation in all animals. Haldane’s rule states that whenever a sex is absent, rare or sterile in a cross between two taxa, that sex is usually the heterogametic sex. Yet, understanding how Haldane’s rule first evolves and whether it is associated to genome wide barriers to gene flow remains a challenging task because this rule is usually studied in highly divergent taxa that no longer hybridize in nature. Here, we address these questions using the meadow grasshopper Pseudochorthippus parallelus where populations that readily hybridize in two natural hybrid zones show hybrid male sterility in laboratorial crosses. Using mitochondrial data, we infer that such populations have diverged some 100,000 years ago, surviving multiple glacial periods in isolated Pleistocenic refugia. Nuclear data shows that secondary contact has led to extensive introgression throughout the species range, including between populations showing hybrid male sterility. We find repeatable patterns of genomic differentiation across the two hybrid zones, yet such patterns are consistent with shared genomic constraints across taxa rather than their role in reproductive isolation. Together, our results suggest that Haldane’s rule can evolve relatively quickly within species, particularly when associated to strong demographic changes. At such early stages of species formation, hybrid male sterility still permits extensive gene flow, allowing future studies to identify genomic regions associated with reproductive barriers.