There has been an emerging interest in stretchable power sources compatible with flexible/wearable electronics. Such power sources must be able to withstand large mechanical strains and still maintain function. Here we report a highly stretchable H3PO4-poly(vinyl alcohol) (PVA) polymer electrolyte obtained by optimizing the polymer molecular weight and its weight ratio to H3PO4 in terms of conductivity and mechanical properties. The electrolyte demonstrates a high conductivity of 3.4 × 10(-3) S cm(-1), and a high fracture strain at 410% elongation. It is mechanically robust with a tensile strength of 2 MPa and a Young's modulus of 1 MPa, and displays a small plastic deformation (5%) after 1000 stretching cycles at 100% strain. A stretchable supercapacitor device has been developed based on buckled polypyrrole electrodes and the polymer electrolyte. The device shows only a small capacitance loss of 5.6% at 30% strain, and can retain 81% of the initial capacitance after 1000 cycles of such stretching.