High entropy alloys (HEAs) have attracted widespread interest due to their unique properties at many different length-scales. Here, we report the fabrication of nanocrystalline (NC) Al0.1CoCrFeNi high entropy alloy and subsequent small-scale plastic deformation behavior via nano-pillar compression tests. Exceptional strength was realized for the NC HEA compared to pure Ni of similar grain sizes. Grain boundary mediated deformation mechanisms led to high strain rate sensitivity of flow stress in the nanocrystalline HEA.