The solubility of zirconium (Zr) in the Nb4AlC3 host lattice was investigated by combining the experimental synthesis of (Nbx, Zr1-x)4AlC3 solid solutions with density functional theory calculations. High-purity solid solutions were prepared by reactive hot pressing of NbH0.89, ZrH2, Al, and C starting powder mixtures. The crystal structure of the produced solid solutions was determined using X-ray and neutron diffraction. The limited Zr solubility (maximum of 18.5% of the Nb content in the host lattice) in Nb4AlC3 observed experimentally is consistent with the calculated minimum in the energy of mixing. The lattice parameters and microstructure were evaluated over the entire solubility range, while the chemical composition of (Nb0.85, Zr0.15)4AlC3 was mapped using atom probe tomography. The hardness, Young's modulus, and fracture toughness at room temperature as well as the high-temperature flexural strength and E-modulus of (Nb0.85, Zr0.15)4AlC3 were investigated and compared to those of pure Nb4AlC3. Quite remarkably, an appreciable increase in fracture toughness was observed from 6.6 ± 0.1 MPa/m(1/2) for pure Nb4AlC3 to 10.1 ± 0.3 MPa/m(1/2) for the (Nb0.85, Zr0.15)4AlC3 solid solution.