When should you break up a monolith into microservices?

We've had this one big application for a few years, and honestly, it's gotten really complicated. Deployments are slower than they should be, and my team doesn't have as much freedom as we'd like. I'm really interested to hear from anyone else who's gone through this. When did you realize it was time to break up your monolith? What was the hardest part of the change, and what advice would you give to a team thinking about doing the same thing?