The difficult part usually isn't the restructuring itself, but understanding what the program is supposed to be doing in the first place. Fortunately, deleting code is one of the best ways to learn about what it's doing. You need some good tooling to do this safely, though.
In my experience this is one of the most offending things in large code bases. I've worked on code that does what it's supposed to do, but you can't see that it's doing it because the solution to the initial problem statement is completely diluted in a mess of factories, abstract classes, gigantic class hierarchies, delegates, and so many other abused patterns.
In some cases the extreme level of abstraction can be justified by the need to have a system that's extensible in many different places. But more often that's not it, it's really just patterns being overly used and abused. You can rewrite the code to be much clearer with less than half the original size and have no negative impact from it.
I mean, anecdotes. I find it funny that in a profession allegedly heavily influenced by science, we keep trading anecdotes(in my experience, "more often than not", etc) instead of having any hard data, tests and experiments to compare.
Rewriting code that works and doesn't need new features is pure waste.