FeCoCrNiMn　high-entropy　alloys　(HEAs)　exhibit　excellent　ductility,　particularly　at　cryogenic　temperatures.　However,　their　yield　strength　is　relatively　low.　In　this　study,　an　inexpensive　element,　phosphorus　(P),　was　added　to　HEAs　at　a　high　concentration　(0.4　%).　The　results　indicate　that　adding　P　not　only　enhances　both　strength　and　ductility,　but　also　avoids　embrittlement.　The　P-added　HEAs　were　single-phase　random　solid　solutions,　with　P　distributed　inside　the　grains　and　partially　segregated　at　the　grain　boundaries.　Within　the　grains,　regions　rich　in　P　and　poor　in　P　were　observed,　along　with　significant　tensile　and　compressive　strain　fields　in　the　P-rich　regions.　These　strain　fields　may　lead　to　large　local　internal　stresses.　The　presence　of　P　prevents　brittleness　due　to　its　specific　atomic　distribution,　whether　in　coarse　or　fine　grains.　The　yield　strength　increased　from　185.27　MPa　in　Pfree　homogenized　HEAs　to　296.1　MPa　in　P-added　HEAs,　representing　an　increase　of　approximately　60　%　at　298　K.　At　77　K,　the　strengths　further　increased,　irrespective　of　grain　size.　Further,　P　added　reduced　the　stacking　fault　energy.　At　room　temperature　(298　K),　P-free　HEAs　formed　dislocation　cells　and　high-density　dislocation　wall　structures,　while　P-added　HEAs　formed　additional　microbands,　deformation　twins,　and　stacking　faults　due　to　increased　lattice　frictional　stress.　P-added　HEAs　demonstrated　excellent　mechanical　properties　at　cryogenic　temperatures,　with　good　strength-ductility　synergy　and　strain-hardening　capacity.　These　enhancements　can　be　attributed　to　the　synergistic　effects　of　nano　deformation　twins,　hierarchical　nano-spaced　stacking　fault　networks,　and　Lomer-Cottrell　locks,　as　well　as　their　extensive　interactions.