Habitat connectivity is important for the survival of species that occupy habitat patches too small to sustain an isolated population. A prominent example of such a species is the European bison (Bison bonasus), occurring only in small, isolated herds, and whose survival will depend on establishing larger, well-connected populations. Our goal here was to assess habitat connectivity of European bison in the Carpathians. We used an existing bison habitat suitability map and data on dispersal barriers to derive cost surfaces, representing the ability of bison to move across the landscape, and to delineate potential connections (as least-cost paths) between currently occupied and potential habitat patches. Graph theory tools were then employed to evaluate the connectivity of all potential habitat patches and their relative importance in the network. Our analysis showed that existing bison herds in Ukraine are isolated. However, we identified several groups of well-connected habitat patches in the Carpathians which could host a large population of European bison. Our analysis also located important dispersal corridors connecting existing herds, and several promising locations for future reintroductions (especially in the Eastern Carpathians) that should have a high priority for conservation efforts. In general, our approach indicates the most important elements within a landscape mosaic for providing and maintaining the overall connectivity of different habitat networks and thus offers a robust and powerful tool for conservation planning.