Network analyses of the phonological mental lexicon show that words are clustered into communities and phonologically dissimilar words can be connected to each other through distant paths. Here we investigate whether behavioral traces of the large-scale structure of the phonological lexicon can be obtained. Participants listened to pairs of spoken words and made phonological similarity judgments for word pairs with varying path lengths and community membership. Path length in the phonological network represented the number of steps needed to traverse from one word to another word in the phonological network. Word pairs were either from the same phonological community or from different communities. Results indicated that participants were sensitive to large-scale structure of the phonological lexicon. Word pairs residing in the same community were more likely rated as similar sounding than word pairs from different communities. Word pairs with longer path lengths were less likely rated as similar sounding than word pairs with shorter path lengths. Computational simulations suggested that the behavioral findings could be accounted for via a spreading activation mechanism implemented on the phonological network. Taken together, our results provide converging evidence that people are sensitive to the large-scale structure of the phonological language network and have implications for our understanding of the nature of phonological similarity representations in the mental lexicon.