Understanding how non-trophic social systems respond to environmental gradients is still a challenge in animal ecology, particularly in comparing changes in species composition to changes in interspecific interactions. Here, we combined long-term monitoring of mixed-species bird flocks, data on participating species evolutionary history and traits, to test how elevation affected community assemblages and interspecific interactions in flock social networks. Elevation primarily affected flocks through reassembling interspecific associations rather than modifying community assemblages. Specifically, flock networks at higher elevations (compared to low elevations) had stronger interspecific associations (larger average weighted degree), network connectivity (enhanced network density) and fewer subnetworks. A phylogenetic and functional perspective revealed that associations between similar species weakened, whereas connections between dissimilar and/or random species were unchanged or strengthened with elevation. Likewise, network assortativity for the traits of vertical stratum and breeding period declined with elevation. The overall pattern is a change from modular networks in the lowlands, where species join flocks with other species that have matching traits, to a more open, random system at high elevations. Collectively, this rewiring of interspecific networks across elevational gradients imparts network stability and resiliency and makes mixed-species flocks less sensitive to local extinctions caused by harsh environments.