Abstract: Landscape connectivity describes the organic connections of landscape components in terms of landscape pattern, process, and function. We used land-cover data in 1986, 2000, and 2011, to study the changes of landscape connectivity for ecological lands (forest, grassland, and wetland) in the middle reaches of the Heihe River based on graph theory. The appropriate landscape threshold was determined by analyzing landscape connectivity changes for different thresholds. Our results indicated that the area of ecological patches, which strongly influenced landscape connectivity, decreased from 1986 to 2011 in our study area. For wetland patches, the area declined more significantly from 2000 to 2011. For grassland, the number of patches decreased and then increased. The area of grassland patches changed slightly, but some patches were fragmented. Distance thresholds had a positive relationship with landscape connectivity. 400 to 800 m was the appropriate distance threshold for the research on species dispersal and ecological flows in the middle reaches of the Heihe River. When 600 m was chosen as the distance threshold, the large patches exerted the most significant influence on regional landscape connectivity level, suggesting they played a key role in regional ecosystem stability and health. Although small ecological patches occupied a small proportion of the total area of ecological patches, it was still necessary to protect and manage these small patches given that they also influenced the maintenance and improvement of regional ecological security pattern. The research was of great importance for ecosystem management in arid areas.