This article presents theoretical and experimental findings on the stability of orthorhombic (Mo1−xNbx)2BC phase in magnetron sputtered coatings, where molybdenum is gradually replaced by niobium. Magnetron co-sputtering of Mo2BC and Nb2BC targets was used to best preserve the metal/non-metal ratio of 1/1. The theoretical calculations were based on replacing Mo atoms in orthorhombic Mo2BC cell, thus creating a (Mo1-xNbx)2BC solid solution. It is predicted to be stable up to 37.5% of Mo atoms replaced by Nb, at which point also the elastic modulus and the shear modulus are the highest. Simultaneously, the enthalpy of formation of this material suggests that it should be more stable than, e.g. the commonly used and studied TiAlN. Experiments have confirmed that orthorhombic (Mo1-xNbx)2BC does not form at high Nb contents, and fcc NbC-like structure was observed instead. All coatings were shown to be columnar with grains in the nanometre range with amorphous regions between the columns. This led to reduced stability of the orthorhombic Mo2BC-like phase compared to the theoretical calculations. At the limit of the stability of the orthorhombic cell, the hardness of the coating was enhanced by 25% and the elastic modulus by 60%. Ab initio calculations indicate that lattice strain is responsible for the mechanical properties’ enhancement.