The ability of group members to discriminate against foreigners is a keystone in the evolution of sociality. In social insects, colony social structure (number of queens) is generally thought to influence abilities of resident workers to discriminate between nestmates and non-nestmates. However, whether social origin of introduced individuals has an effect on their acceptance in conspecific colonies remains poorly explored. Using egg-acceptance bioassays, we tested the influence of social origin of queen-laid eggs on their acceptance by foreign workers in the ant Formica selysi. We showed that workers from both single- and multiple-queen colonies discriminated against foreign eggs from single-queen colonies, whereas they surprisingly accepted foreign eggs from multiple-queen colonies. Chemical analyses then demonstrated that social origins of eggs and workers could be discriminated on the basis of their chemical profiles, a signal generally involved in nestmate discrimination. These findings provide the first evidence in social insects that social origins of eggs interfere with nestmate discrimination and are encoded by chemical signatures.