Background: Host-parasite coevolution can lead to local adaptation of either parasite or host if there is specificity (GxG interactions) and asymmetric evolutionary potential between host and parasite. This has been demonstrated both experimentally and in field studies, but a substantial proportion of studies fail to detect such clear-cut patterns. One explanation for this is that adaptation can be masked by counter-adaptation by the antagonist. Additionally, genetic architecture underlying the interaction is often highly complex thus preventing specific adaptive responses. Here, we have employed a reciprocal cross-infection experiment to unravel the adaptive responses of two components of fitness affecting both parties with different complexities of the underlying genetic architecture (i.e. mortality and spore load). Furthermore, our experimental coevolution of hosts (Tribolium castaneum) and parasites (Nosema whitei) included paired replicates of naive hosts from identical genetic backgrounds to allow separation between host- and parasite-specific responses. Results: In hosts, coevolution led to higher resistance and altered resistance profiles compared to paired control lines. Host genotype × parasite genotype interactions (GH× GP) were observed for spore load (the trait of lower genetic complexity), but not for mortality. Overall parasite performance correlated with resistance of its matching host coevolution background reflecting a directional and unspecific response to strength of selection during coevolution. Despite high selective pressures exerted by the obligatory killing parasite, and host- and parasite-specific mortality profiles, no general pattern of local adaptation was observed, but one case of parasite maladaptation was consistently observed on both coevolved and control host populations. In addition, the use of replicate control host populations in the assay revealed one case of host maladaptation and one case of parasite adaptation that was masked by host counter-adaptation, suggesting the presence of complex and probably dynamically changing fitness landscapes. Conclusions: Our results demonstrate that the use of replicate naive populations can be a useful tool to differentiate between host and parasite adaptation in complex and dynamic fitness landscapes. The absence of clear local adaptation patterns during coevolution with a sexual host showing a complex genetic architecture for resistance suggests that directional selection for generality may be more important attributes of host-parasite coevolution than commonly assumed. © 2012 Bérénos et al; licensee BioMed Central Ltd.