Ternary Nb1-xAlxN films were grown on single-crystal MgO(001) substrates by reactive triode sputtering in an Ar+N-2 gas mixture. A phase spread deposition technique was employed to fabricate films with a composition gradient along the length of a substrate. For a deposition temperature of 500 degrees C, X-ray diffraction (XRD) showed that the compound films had the cubic B1 structure for Al fractions in the range from 0 < x < 0.60. The lattice parameter decreased with increasing x, from 4.41 Angstrom at x = 0 to approximately 4.26 Angstrom for x = 0.59. A new ternary Nb-Al-N phase was discovered in a narrow composition range around 63% Al. This phase crystallized in an fee structure with a unit cell size of 4.15 + 0.02 Angstrom and was stabilized possibly by epitaxy to the single crystal substrate. For Al fractions beyond 65% XRD indicated nanocrystalline films having the hexagonal wurtzite structure. Determination of elastic strain, crystallographic tilt and microstructural quality was performed by high resolution XRD reciprocal space mapping. Epitaxial films with x < 0.50 grew essentially unstrained, with the mismatch accommodated by means of misfit dislocations giving the film a mosaic character. Growth modes and phase decomposition paths of the metastable BI films at x less than or equal to 0.60, as well as the structure of the new phase at x = 0.63, were assessed by planar and cross sectional transmission electron microscopy.