Behavioral “traditions”, i.e. behavioral patterns that are acquired with the aid of social learning and that are relatively stable in a group, have been observed in several species. Recently, however, it has been questioned whether non-human social learning is faithful enough to stabilize those patterns. The observed stability could be interpreted as a result of various constraints that limit the number of possible alternative behaviors, rather than of the fidelity of transmission mechanisms. Those constraints can be roughly described as “internal”, such as mechanical (bodily) properties or cognitive limitations and predispositions, and “external”, such as ecological availability or pressures. Here we present an evolutionary individual-based model that explores the relationships between the evolution of faithful social learning and behavioral constraints, represented both by the size of the behavioral repertoire and by the “shape” of the search space of a given task. We show that the evolution of high-fidelity transmission mechanisms, when associated with costs (e.g. cognitive, biomechanical, energetic, etc.), is only likely if the potential behavioral repertoire of a species is large and if the search space does not provide information that can be exploited by individual learning. Moreover we show how stable behavioral patterns (“traditions”) can be achieved at the population level as an outcome of both high-fidelity and low-fidelity transmission mechanisms, given that the latter are coupled with a small behavioral repertoire or with a search space that provide substantial feedback. Finally, by introducing the possibility of environmental change, we show that intermediate rates of change favor the evolution of faithful social learning.