Iron-chromium-aluminum (FeCrAl) alloys are promising as corrosion- and oxidation-resistant materials for high-temperature applications. However, further design and improvement of FeCrAl-based materials require a delicate balance between workability, weldability, and a propensity for $\alpha$′-phase formation. Here, a series of advanced oxidation-resistant FeCrAl alloys were produced and investigated. FeCrAl variants with aluminum (+ 2%), niobium (+ 1%), and titanium carbide (+ 0.1%, + 0.3%, and + 1%) additions were characterized in detail before and after controlled laser-beam welding; tensile tests with digital image correlation, scanning electron microscopy-electron back scattered diffraction analysis, and fractography analysis were conducted. All investigated alloys demonstrated a yield stress of over 500 MPa in the weldment; no welding-induced cracking was observed. However, it was shown that increasing the aluminum content to over 5% was detrimental to the material’s integrity, leading to a brittle fracture mechanism and decreased ductility in the weldment. At the same time, the niobium and titanium carbide additions helped prevent grain growth and reduce local softening (yield stress reduction) in the heat-affected zone. The 1% titanium carbide addition also effectively refined grain size in the weldment.