Taguchi and post-heat treatment methods have been used in this study to optimize the metal inert gas (MIG) welding joints between SUS304 austenite stainless steel and plain carbon SS400 steel using AWS ER 308L filler wire. The dissimilar welding joints’ microstructure and tensile strength have been examined. The findings show that the fast cooling of the weld joint and the ferrite-forming element of the filler wire cause the dendrites’ δ-ferrite phase to emerge on both the weld bead and the heat-affected zone (HAZ) of the SUS304 side. The stickout parameter has the largest impact on the ultimate tensile strength (UTS), next to the welding speed, welding voltage, and welding current, due to the strong impact of the heat distribution. The optimal welding parameters are a welding current of 105 A, a welding voltage of 14.5 V, a stickout of 12 mm, and a welding speed of 420 mm/min, producing the UTS value of 445.3 MPa, which is close to the predicted value of 469.2 ± 53.6 MPa. Post-heat treatment with an annealing temperature that is lower than 700 °C could improve the optimized weld joints’ strength by up to 5%. The findings may provide a more realistic understanding of the dissimilar welding technology.