Social relationships can have important consequences for fitness in animals. Whilst numerous studies have shown that individuals often join larger groups in response to perceived predation risk (i.e. fear of predation), the importance of predation risk in driving the formation and stability of social relationships within groups has been relatively ignored. We experimentally tested how predation threat influenced fine-scale social network structure using Trinidadian guppies (Poecilia reticulata). When perceived predation risk was high, individuals developed stable and more differentiated social ties compared to when perceived risk was low. Intriguingly, social differentiation coincided with shoals being somewhat smaller under high-perceived risk, suggesting a possible conflict between forming stable social relationships and larger social groups. Individuals most at risk of predation (large and bold individuals) showed the most exaggerated responses in several social measures. Taken together, we provide the first experimental evidence that proximate risk of predation can increase the intensity of social relationships and fine-scale social structure in animal populations.