I get the impression that the code base on which you pulled off the "large-scale invasive refactoring" was not initially under test, else why would the cynical engineers think it could not be done. So did you have to bring the legacy code under test first?