Corrosion-resistant alloys with high strength and large ductility are desirable for applications in harsh environments where high structural load-carrying capacity is required. In this work, we designed an L12-strengthened high-entropy alloy (HEA) of composition (NiCo)77Cr13Al5Nb5 (at.%) that combines excellent mechanical properties and good corrosion resistance. The formation of a thin passive film of non-stoichiometric compounds with an amorphous structure, characterized by an enrichment of Cr2O3 and Nb2O5, contributes to the superior localized corrosion resistance. The precipitation strengthening brought about by coherent L12 particles and the multi-stage plastic deformation dominated by stacking faults (SFs) provides ultrahigh strength and appreciable ductility, respectively.