This chapter will introduce and discuss in detail common challenges that are uniquely associated with applying coevolution for search in problem solving. The chapter starts with a general introduction of challenges that affect the performance of coevolutionary search algorithms in the same manner that one faces in evolutionary search algorithms. The next section introduces specific challenges associated with the use of coevolution. They are collectively referred to as coevolutionary pathologies and will be informally discussed. The following section will introduce recent formal studies that have provided tools to uncover and analyse structures in coevolution that are informative towards deeper understanding of coevolutionary search processes. In particular, more formal discussions of selected coevolutionary pathologies are provided. The last section will close with remarks of general approaches that have been designed to address these coevolutionary pathologies and as such improve search performance.