This paper presents a heuristic method for minimization of incompletely specified Mealy finite state machines. In this method, such optimization criteria as the speed and possibility of merging other states are taken into account already at the stage of minimizing internal states. Algorithms for the estimation of optimization criteria values are described. The proposed method is based on two states merging. Experimental results for two styles of state encoding and two types of programmable structures are presented. The results show that this approach to minimization of FSM in most of cases is more effective than classical methods in respect of FSM performance.