The mechanical behavior of nanocrystalline (NC) metals has attracted widespread interest, though the majority of efforts have focused on (nominally) pure metals. By comparison, the mechanisms of deformation and strengthening in NC alloys, especially those with high segregation propensity and strong chemical interactions, are less well understood. Here we present a quantitative investigation on the mechanical behavior of such an alloy system. NC Al-O thin films are synthesized by means of confocal co-sputtering, which enables a wide-range and quasi-independent control over impurity content and grain size. Detailed characterization combining transmission electron microscopy with three-dimensional atom probe tomography identify the multiple morphologies of O impurities in a composite-like microstructure, including nanosized -Al2O3 precipitates, O-rich clusters segregated along grain boundaries, and O solute atoms inside Al grains. Individual contributions of these strengthening features to the mechanical properties of NC Al-O thin films, as measured by instrumented nanoindentation, are then well delineated by a microstructure-informed analytical model. Dislocations emitted from grain boundaries are pinned by the stronger obstacles and cut through the weaker, and we show that the strong chemical interactions of this Al-O system play a dominant role in its pronounced strengthening capability. The influence of O impurities on the plasticity and deformation mechanisms in NC Al films is also discussed based on microtensile testing.