Humans have impacted most of the planet, and the ensuing fragmentation results in small, isolated habitat patches posing a risk of genetic diversity loss, inbreeding, and genetic load. Understanding how natural and anthropogenic landscape features affect gene flow among habitat patches is critical for maintaining connectivity. Genome-wide data are required to comprehend the impacts of recent fragmentation, which can be challenging when only non-invasive samples are available. Here, we build upon advancements in conservation genomics to address connectivity of two large herbivores, gaur (Bos gaurus) and sambar (Rusa unicolor) in central India. Given their habitat associations, we expected these species to respond similarly to habitat fragmentation. We used faecal-DNA and methylation-based host-DNA enrichment with modified ddRAD protocol to generate genome-wide single-nucleotide polymorphism (SNP) data for 124 gaur and 99 sambar individuals. Our findings reveal that gaur populations in central India are fragmented, displaying high genetic differentiation, with drift significantly affecting small populations like Umred Karhandla Wildlife Sanctuary. Although sambar shows low genetic structure, another small population, Bor Tiger Reserve is genetically differentiated. Our results suggest that although land cover change and roads restrict animal movement, the extent of this impact varies across the two species. We show that different species respond differently to landscape features, even with similar habitat associations. We highlight small and isolated populations requiring urgent conservation intervention. Such multi-species approaches enhance our understanding of cross-species connectivity patterns. We suggest shifting from single-species to multi-species holistic conservation approach in rapidly developing landscapes to better manage co-occurring endangered species.