A novel construction for encoded tamed frequency modulation (TFM) is introduced which is based on the principles of generalized concatenation. The inner TFM is partitioned into nested subsystems which increases the free Euclidean distances. In order to obtain a large distance among the nested TFM subsystems, the scrambler matrices have to be computed which transfer the original TFM into the equivalent TFM with better partitioning properties. Then outer convolutional codes with different error-correcting capabilities are used to protect the partitioning. The new concatenated and generalized concatenated constructions were simulated in an additive white Gaussian noise channel. A multistep decoding algorithm based on soft-output demodulation was used. We present various simulation results which show a significant coding gain in comparison with the best known trellis codes having the same trellis state complexity.