The key to the survival of a species lies in understanding its evolution in an ever-changing environment. We report a theoretical model that integrates frequency-dependent selection, mutation, and asexual reproduction for understanding the biological evolution of a host species in the presence of parasites. We study the host-parasite coevolution in a one-dimensional genotypic space by considering a dynamic and heterogeneous environment modeled using a fitness landscape. It is observed that the presence of parasites facilitates a faster evolution of the host population toward its fitness maximum. We also find that the time required to reach the maximum fitness (optimization time) decreases with increased infection from the parasites. However, the overall fitness of the host population declines due to the parasitic infection. In the limit where parasites are considered to evolve much faster than the hosts, the optimization time reduces even further. Our findings indicate that parasites can play a crucial role in the survival of its host in a rapidly changing environment. © 2020 Author(s).