There is no way to do this gradually.

Don't try to get everyone's buy in. You won't.

This needs to be enforced from the top. And immediately to stop the bleeding.

If you add tests, especially when you get to hundreds or thousands it can indeed get chaotic, try Tesults (tesults.com) for managing them along with results. Contact me if your team is very small for freebies (I’m associated).