Since modern programmable devices contain embedded memory blocks, there exists a possibility to implement Finite State Machines (FSM) using such blocks. The size of the memory available in programmable devices is limited, though. The paper presents a general method for the synthesis of sequential circuits using embedded memory blocks. The method is based on the serial decomposition concept and relies on decomposing the memory block into two blocks: a combinational address modifier and a smaller memory block. An appropriately chosen decomposition strategy may allow reducing the required memory size at the cost of additional logic cells for address modifier implementation. This makes possible implementation of FSMs that exceed available memory by using embedded memory blocks and additional programmable logic.