Why humans are prone to cooperate puzzles biologists, psychologists and economists alike. Between-group conflict has been hypothesized to drive within-group cooperation. However, such conflicts did not have lasting effects in laboratory experiments, because they were about luxury goods, not needed for survival ("looting"). Here, we find within-group cooperation to last when between-group conflict is implemented as "all-out war" (eliminating the weakest groups). Human subjects invested in helping group members to avoid having the lowest collective pay-off, whereas they failed to cooperate in control treatments with random group elimination or with no subdivision in groups. When the game was repeated, experience was found to promote helping. Thus, not within-group interactions alone, not random group elimination, but pay-off-dependent group elimination was found to drive within-group cooperation in our experiment. We suggest that some forms of human cooperation are maintained by multi-level selection: reciprocity within groups and lethal competition among groups acting together.