Ultra-high strength steels (UHSS) have a determining role in construction and industry. Furthermore, welding as the primary joining process for steel has a similar role in promoting its applications. Therefore, welded UHSS have a vital role in related applications. However, due to their complex microstructures, these steels are more prone to harmful effects of welding heat input on the mechanical properties compared to mild steels. Thus, identifying the correlations between the microstructural transformations triggered by the heat input and the mechanical properties can lead to new insights and hindering the drawbacks. This study investigates the microstructures and mechanical properties of S960 (with a severe softening after welding) and S1100 (with a negligible decrease of the mechanical properties after welding) to understand the mechanisms behind the softening of welded UHSS. Microstructural analysis showed the formation of soft phases, e.g., ferrite and granular bainite, as the primary reason for the softening. Furthermore, tempered forms of martensite and bainite resulted in the simultaneous decrease of hardness and notch toughness. Finally, the applicabilities of two experimental approaches to predict hardness from microstructural constituents were evaluated for welded S960 and S1100 and proved to have relatively good reliability to detect their HAZ softened spots.