In the world where code is legacy, the minute you deploy it to a production system. Every developer is touching some piece of code which is legacy and does not have sufficient test coverage. Team might be running manual test for their releases. But as we know running manual test might take significant amount of time. It would make continuous development/deployment impossible for any agile team. I would think any agile practice would fail without proper automated test coverage. Forget about teams who does not have manual testcases.
Imagine above project where we had 10 features to start with and team slowly developed more functionality. Our manual testing time also gradually grew from 1 hour to 4 hours. The amount of manual testing would go up with every feature unless team takes measures to stop this from happening.
In my old project we started with identifying easy to automate, we started automating steps which were repeated in most of the testcases. i.e. login, mouse clicks and loading of menu bars etc. Our application was very difficult to automate because it was not written to keep automation in mind.
During step identification process, we decided to develop automated tests for our new features. We were being able to stop our situation from deteriorating. Our goal was to add automated test for all new functionality we were developing. This was the most difficult step. We modified our DoD ( Definition of Done) too.
Honestly this was big step for us and we gained lots of confidence by doing it. We slowly used our Kaizen time to convert existing manual testcases over the period of time.
Trying doing the same thing for your codebase, I am sure you would see success too. Try reading http://www.thoughtworks.com/insights/blog/test-automation-who-should-be-involved article.