The next generation of deformable and shape-conformable electronics devices will need to be powered by batteries that are not only flexible but also foldable. Here we report a foldable Lithium-Sulfur (Li-S) rechargeable battery, with the highest areal capacity  (~3 mAh cm^-2) reported to date among all types of foldable energy-storage devices. The key to this result lies in the use of fully-foldable and super-elastic carbon nanotube current-collector films and impregnation of the active materials (S and Li) into the current-collectors in a checkerboard pattern, enabling the battery to be folded along two mutually orthogonal directions. The carbon nanotube films also serve as the sulfur entrapment layer in the Li-S battery. The foldable battery showed < 12% loss in specific capacity over 100 continuous folding and unfolding cycles. Such shape-conformable Li-S batteries with significantly greater energy density than traditional lithium-ion batteries could power the flexible and foldable devices of the future including laptops, cell-phones, tablet computers, surgical tools and implantable bio-medical devices.