In this paper, we introduce the concept of (self-)reconfigurable finite state machines as a formal model to describe state-machines implemented in hardware that may be reconfigured during operation. By the advent of reconfigurable logic devices such as FPGAs, this model may become important to characterize and implement (self-)reconfigurable hardware. An FSM is called (self-)reconfigurable if reconfiguration of either output function or transition function is initiated by the FSM itself and not based on external reconfiguration events. We propose an efficient hard-ware realisation and give algorithmic solutions and bounds for the reconfiguration overhead of migrating a given FSM specification into a new target FSM.