Transitioning to asynchronous programming model

Question

Our team is mantaining and developing a .NET web service written in C#. We have stress tested the web service's farm and we have evidence that the actual architecture doesn't scale well, as the number of requests are constantly increasing.

We analyzed Martin Fowler's conclusion in this article, and our team feels that migrating to an asynchronous programming model such as the one described could be the right direction to point to for our service too. My question is: do you think that this "switch" needs a complete rewrite of the application? Has been someone of you been able to adopt APM without rewriting everything and has some insight to share?

Thank you in advance