Here's the way I see it.
If the output of a system is determined by its current inputs, you can form a truth table and that truth table can be done by a logic tree (if..if..else....)
If some history is involved, the system has to have memory. And then, the output depends on current inputs and the values in memory.
If there is not just one output but multiple things have to happen depending on inputs and historical conditions, now you need a way to name each resulting condition depending on the trail(s) that can lead to that condition. You need to be able to name them so that you can reason about what should happen on further inputs in such conditions.
To make it possible for multiple people to talk about such systems, you need a paradigm. A way of looking at a system as a set of these conditions we talked about and the events that cause movement between these conditions, along with any other actions that happen along with the movement.
That paradigm is a state machine. State machines can have different states (conditions in the previous paragraph), events/signals (inputs) and transitions between states, along with possible actions on exit of a state, entry of a state, transition, etc.
Then we have UML having state charts, tools to generate code from visual state charts, check for dead-end states, impossible states, etc.
Essentially, FSMs give a new language for thought about systems and for expression of such thought. Something more than just code can do.
I tried to give you a justification that FSMs are a natural outcome !