AbstractMost social interactions do not take place at random. In many situations, individuals choose their interaction partners on the basis of phenotypic cues. When this happens, individuals are often homophilic, that is, they tend to interact with individuals that are similar to them. Here we investigate the joint evolution of phenotypic cues and cue-dependent interaction strategies. By a combination of individual-based simulations and analytical arguments, we show that homophily evolves less easily than earlier studies suggest. The evolutionary interplay of cues and cue-based behaviour is intricate and has many interesting facets. For example, an interaction strategy like heterophily may stably persist in the population even if it is selected against in association with any particular cue. Homophily persisted for extensive periods of time just in those simulations where homophilic interactions provide a lower (rather than a higher) payoff than heterophilic interactions. Our results indicate that even the simplest cue-based social interactions can have rich dynamics and a surprising diversity of evolutionary outcomes.