We report on the layer-by-layer growth of single-crystal Al2O3 thin-films on Nb (110). Single-crystal Nb films are first prepared on A-plane sapphire, followed by the evaporation of Al in an O2 background. The first stages of Al2O3 growth are layer-by-layer with hexagonal symmetry. Electron and x-ray diffraction measurements indicate the Al2O3 initially grows clamped to the Nb lattice with a tensile strain near 10%. This strain relaxes with further deposition, and beyond about 5 nm we observe the onset of island growth. Despite the asymmetric misfit between the Al2O3 film and the Nb under-layer, the observed strain is surprisingly isotropic.