High strength combined with sufficient toughness is a fundamental prerequisite for steel in the field of lightweight construction. Joining high-strength steels by means of welding requires the use of highly advanced filler metals and a stress-relief post-weld heat treatment (PWHT) for optimum performance of the joint. However, such a heat treatment can lead to embrittlement in the weld metal. In this context, the present work deals with the influence of different PWHT holding temperatures on the microstructure and mechanical properties of a high-strength multipass all-weld metal to reveal the embrittlement phenomena. The all-weld metal was fabricated via gas metal arc welding using a metal cored wire with a minimum yield strength of 690 MPa. Charpy V-notch impact testing and tensile testing were carried out to characterize the strength and toughness of the all-weld metal in the as-welded condition and after a 2 h stress-relief PWHT at 520 °C, 580 °C, and 620 °C. The microstructure was characterized utilizing high-resolution techniques such as atom probe tomography and high-energy X-ray diffraction. The strength and toughness of the all-weld metal both decrease after PWHT with different holding temperatures. The cause for the observed embrittlement was found to be the formation of Mn-rich cementite precipitates. These carbides increase in size and phase fraction with increasing holding temperature and lead to a brittle transcrystalline cleavage fracture. Consequently, it was concluded that a gas metal arc welded joint with the investigated filler metal should not be exposed to stress-relief PWHT at temperatures higher than 580 °C.