A State Machine is made up of States, Transitions, Entry Actions, and Exit Actions. States represent different conditions or stages the machine can be in, Transitions define how the machine moves from one state to another, and Entry and Exit Actions are tasks executed when entering or exiting a state. These components collectively describe the primary structure of a State Machine in a workflow.