That depends on your problem. I've seen useful state machines. I've seen someone implement a simple decoder as a complex any-to-any state machine that couldn't be understood - a single switch statement would have been better. Nothing about state machines, but some people have a hammer and are determined to prove it can drive any screw - it works but isn't how you should do it.
I've adopted a rule of thumb to have a very low bar to skip straight to writing a state machine. I've never once regretted it, personally. I'm sure they can be misused but I haven't came across that.