Stretchable conductors are essential components in next-generation deformable and wearable electronic devices. The ability of stretchable conductors to achieve sufficient electrical conductivity, however, remains limited under high strain, which is particularly detrimental for charge storage devices. In this study, we present stretchable conductors made from multiple layers of gradient assembled polyurethane (GAP) comprising gold nanoparticles capable of self-assembly under strain. Stratified layering affords control over the composite internal architecture at multiple scales, leading to metallic conductivity in both the lateral and transversal directions under strains of as high as 300%. The unique combination of the electrical and mechanical properties of GAP electrodes enables the development of a stretchable lithium-ion battery with a charge-discharge rate capability of 100 mAh g-1 at a current density of 0.5 A g-1 and remarkable cycle retention of 96% after 1000 cycles. The hierarchical GAP nanocomposites afford rapid fabrication of advanced charge storage devices.