In the engineering design of machines and vehicles, the technologies involving vibration and noise reduction receive considerable attention as they can prevent undesirable fatigue failures and offer more comfort to the users. Compared with other damping alloys, high Mn steel has been intensively studied because its high strength and excellent damp capacity can be achieved simultaneously at a low cost. Particularly, it has a strong potential of circumventing the long-existing trade-off of strength and damping capacity for more applications in the new circumstance. In this study, the microstructures and damping and mechanical properties of a novel hot-rolled Nb-alloyed high Mn steel annealed at the temperature range of 750-1050^oC were investigated. Heterogeneous recrystallization occurred during hot rolling, resulting in the formation of recrystallized bands along the rolling direction, in which fine lamellar ε martensite grains were interwoven with austenite; the coarse unrecrystallized ε martensite blocks were located between the bands. The latter was reversely transformed to the coarse austenite with a single orientation, remained unrecrystallized, and transformed back to the coarse highly-dislocated ε martensite blocks during the annealing below 850^oC. Conversely, the ε martensite blocks reversely transformed the austenite grains partially and completely recrystallized to form even more refined grains with multi-orientations during annealing at 950 and 1050^oC, respectively. Thus, the recrystallized austenite grains transformed to fine ε lamellar martensite, and the austenite grains were retained with multi-orientations, both having a low density of dislocation. Consequently, the higher annealing temperature led to higher damping capacity but lower strength; whereas, the partial recrystallization occurring during annealing at 950^oC resulted in the best combination of mechanical and damping properties. Therefore, this indicates that tailoring the extent of recrystallization via the Nb-alloying and annealing process for high Mn steel can be an effective method to achieve different combinations of strength and damping capacity.