The strong demand for portable, ultra-thin, lightweight, flexible and stretchable devices, raises the need for new material and design concepts in battery technology that offer multi-functionality such as simultaneous electrochemical and mechanical functions. A key imperative in the development of the all-solid-state lithium ion batteries (LIBs) is the replacement of the traditional organic liquid electrolyte with high performance solid electrolyte. In this study, flexible and stretchable Li ion batteries are developed, based on solid nanocomposite polymer electrolyte (1% graphene oxide nanosheets in polyethylene oxide host), exhibiting capacities higher than 0.1 mAh cm^-2 and excellent cycling stability over 100 charge/discharge cycles. Improvement in internal impedance of the battery is observed with the addition of 1% graphene oxide nanosheets to the polymer electrolyte. The energy density of the fabricated LIB is measured to be 4.8 mWh cm^-3 at room temperature. The laminated LIB exhibits robust mechanical flexibility, good voltage retention over high bending and stretching cycles (i.e. over 6000 cycles) and good electrochemical performance in different configurations. Finite element analysis of the flexible and stretchable batteries provides critical insights into the evolution of mechanical stresses during lamination, bending and stretching.