Co-evolutionary models have received increasing attention in the research on evolutionary algorithms (EAs), since they seem to offer novel ideas for how to overcome some of the problems inherent in “classical” EAs. This article is concerned with one type of co-evolutionary model, based on the use of hosts and parasites, which allows co-evolution of a population of candidate problem solutions and a population of fitness cases. Although host-parasite algorithms have shown promising results in previous research, there is a lack of work aimed at formalizing this class of algorithms, and studying aspects of their behaviour in more detail. To help remedy this situation, this article explores the role of problem asymmetry in limiting the progress of host-parasite search, and shows how a suite of co-evolutionary function optimization problems can be used to study the behaviour of host-parasite algorithms under varying levels of asymmetry. The article also presents the asymmetry-handling host-parasite algorithm (AHPA) and a set of experiments aimed at identifying the conditions under which AHPA consistently gives improvements over simple host-parasite algorithms.