Modern digital systems can be viewed as compositions of combinational and sequential blocks. In the article, we discuss a case when sequential blocks are represented using a model of Mealy finite-state machine (FSM). It is very important to improve such FSM characteristics as the number of used logic elements, operating frequency and power consumption. This article proposes a novel design method which allows diminishing the number of look-up table (LUTs) and increasing the operating frequency of multilevel LUT-based Mealy FSMs. The method is based on simultaneous use of such methods of structural decomposition as the transformation of states into FSM outputs and twofold state encoding. The proposed method results in three-level logic circuits of Mealy FSMs with regular systems of interconnections. Each function for any level of logic is implemented using a single LUT. An example of FSM synthesis with the proposed method is given. The experiments with standard benchmarks were conducted. The results of experiments show that the proposed approach leads to decreasing LUT counts from 11.9% to 62.6%. Also, it leads to increasing the operating frequency from 11.77% to 18.43% on average compared with other investigated approaches (Auto and One-hot of Vivado, JEDI, and replacement of FSM inputs and encoding the collections of outputs). The economy in used LUTs and gain in operating frequency grow with the growth of the FSM complexity.