How do you approach refactoring an ugly procedure/query?

I've inherited a database which contains several procedures which are 1000-1500 lines long, with complex nested sub-selects going up to 7 or 8 levels deep in places. I desperately need to refactor them for my own sanity, but how can I begin to do this with any level of confidence that they still work the same? I would write unit tests if this were .Net - do you recommend a similar approach?