This paper argues that visual art coevolved with typically human ways of social organization and cooperation strategies. My argument, in brief, is that Late Pleistocene human groups became organised in band societies that established networks of indirect reciprocal cooperation, which favoured cultural strategies of individual recognition such as social markers, e.g. styles of personal ornamentation. These early forms of visual art, by conveying information about social identity, became important in recalling and assessing individual interactions in cooperative networks. I also argue that as a cultural strategy, visual art could have been adaptive by reducing risk of aggression and increasing resource acquisition through exchange. As other evolved cultural traits, like tool-making and cooking, visual art too could have had an important impact on shaping modern human cognition and behaviour.