First write a regression test suite. You need protection from introducing new bugs as you refactor your code. Some general tips:

• Ensure each module can be easily tested in isolation.
• Interfaces matter. Minimize the exposure of implementation details; provide stable interfaces to protect the remainder of the program from the details of the implementation (which are likely to change) - don't just provide full access to the data used in the implementation. (See Information hiding).

See also:

• Splitting program into modules
• Code Structure Changes
• On Interfaces and APIs
• Swallowing an elephant in 10 easy steps by ELISHEVA (Describes how she tackles big problems to keep moving forward rather than going around in circles)
• Effective Automated Testing