The processes governing social interactions and the resulting relationships among members of colonially organized animals are largely unknown. Using network analytical tools we investigated fundamental components of social structure in a highly fluid fission–fusion society. We constructed a social network and studied the relative importance of sex and age class, fine-scale site fidelity and male territory distribution in a breeding colony of the Galápagos sealion, Zalophus wollebaeki. The social system was partitioned into a hierarchy with at least three levels. The outermost level of organization was given by a single social network, where all individuals of the population were interconnected. This level split into communities and further into cliques. Sex and age class influenced social structure at the population level, whereas fine-scale site fidelity explained most of the structure found at the community level. None of these assortment variables could account for clique structure, which might therefore be explained in terms of individual preferences, genetic relatedness or a combination of both. Male territories did not form the basic unit of social structure, but appeared simply to be superimposed on the structural backbone formed by females and young.