The hot deformation behavior of a newly designed Fe–5Mn–3Al–0.1C (wt.%) medium manganese steel was investigated using hot compression tests in the temperature range of 900 to 1150◦ C, at constant strain rates of 0.1, 1, 2.5, 5, 10, and 20 s−1. A detailed analysis of the hot deformation parameters, focusing on the flow behavior, hot processing map, dynamic recrystallization (DRX) critical stress, and nucleation mechanism, was undertaken to understand the hot rolling process of the newly designed steel. The flow behavior is sensitive to deformation parameters, and the Zener–Hollomon parameter was coupled with the temperature and strain rate. Three-dimensional processing maps were developed considering the effect of strain and were used to determine safe and unsafe deformation conditions in association with the microstructural evolution. In the deformation condition, the microstructure of the steel consisted of δ-ferrite and austenite; in addition, there was a formation of DRX grains within the δ-ferrite grains and austenite grains during the hot compression test. The microstructure evolution and two types of DRX nucleation mechanisms were identified; it was observed that discontinuous dynamic recrystallization (DDRX) is the primary nucleation mechanism of austenite, while continuous dynamic recrystallization (CDRX) is the primary nucleation mechanism of δ-ferrite. The steel possesses unfavorable toughness at the deformation temperature of 900◦ C, which is mainly due to the presence of coarse κ-carbides along grain boundaries, as well as the lower strengthening effect of grain boundaries. This study identified a relatively ideal hot processing region for the steel. Further exploration of hot roll tests will follow in the future.