As part of a study to assess NiAl-based composites as potential high-temperature structural materials, the mechanical properties of polycrystalline NiAl reinforced with 30 vol.% continuous single crystal Al2O3 fibers were investigated. Composites were fabricated with either a strong or weak bond between the NiAl matrix and Al2O3 fibers. The effect of interfacial bond strength on bending and tensile properties, thermal cycling response, and cyclic oxidation resistance was examined. Weakly-bonded fibers increased room-temperature toughness of the composite over that of the matrix material but provided no strengthening at high temperatures. With effective load transfer, either by the presence of a strong interfacial bond or by remotely applied clamping loads, Al2O3 fibers increased the high-temperature strength of NiAl but reduced the strain to failure of the composite compared to the monolithic material. Thermal cycling of the weakly-bonded material had no adverse effect on the mechanical properties of the composite. Conversely, because of the thermal expansion mismatch between the matrix and fibers, the presence of a strong interfacial bond generated residual stresses in the composite that lead to matrix cracking. Although undesirable under thermal cycling conditions, a strong interfacial bond was a requirement for achieving good cyclic oxidation resistance in the composite. In addition to the interfacial characterization, compression creep and room temperature fatigue tests were conducted on weakly-bonded NiAl/Al2O3 composites to further evaluate the potential of this system. These results demonstrated that the use of A12O3 fibers was successful in improving both creep and fatigue resistance.