Built by outside powers and targeted against local insurgents, the new national armies of Afghanistan and Iraq are fragile institutions. The legitimacy of these forces is limited in the deeply divided societies in which they exist. Whereas low levels of legitimacy exert a disintegrative pressure upon an army, cohesion counterweighs such pressure. This article engages the theory of military unit cohesion for the purpose of increasing understanding of the challenges to cohesion faced by the new armies of Afghanistan and Iraq. Two main sources of legitimacy for the new armies are discussed: the (ethnic/sectarian) composition of the forces, and their respective missions. Challenges to cohesion are found to depend on how soldiers are recruited and units composed: ethnically/sectarian mixed units may disintegrate because of weak horizontal cohesion; homogeneous units (particularly when recruited as groups and not individually) may splinter off because of weak vertical cohesion. The article also argues that promoting an image of the army as ‘national’ within a society may reduce disintegrative pressures.