Whenever I do refactoring, the first step is always the same. I need to build a solid set of tests for that section of code. The tests are essential because even though I follow refactorings structured to avoid most of the opportunities for introducing bugs, I'm still human and still make mistakes. Thus I need solid tests. (Refactoring: Improving the Design of Existing Code, Fowler et al, 1999)
When I first read Refactoring, I believed that tests were a necessary prerequisite before making structural changes to the code. However, when I worked with legacy code this often left me paralysed: I can't change the code because it doesn't have any tests, but I can't write the tests because I can't change the code.
Reading Working Effectively with Legacy Code gave me escape route. I could write simpler characterization tests to capture the behaviour of existing code and then refactor. Instead of writing a unit test to capture correctness, I could write a characterization test to capture the behaviour; if the behaviour is preserved, I've not broken the code.
In the years since Refactoring was written tools (such as Eclipse, IntelliJ and Resharper) have well and truly crossed the Rubicon. Over the years I've used these tools, they've gradually earned my trust to the point where I wouldn't consider writing Java/C# without the aid of such as tool.
Using a refactoring tool changes the way you approach code. I feel quite confident in saying that refactoring doesn't always require tests . Instead of considering legacy code as an inanimate collection of methods, I view it as a lump of putty I can shape as needed. Refactoring tools allow you to quickly explore the design space before settling on a decision.
 In so much as you trust the refactoring tool! There's always the chance that the refactoring tool will break your code, but I believe these chances are vanishingly small in most circumstances (just don't use reflection!).