Two-dimensional (2D) layered materials, such as MoS2, are greatly attractive for flexible devices due to their unique layered structures, novel physical and electronic properties, and high mechanical strength. However, their limited mechanical strains (<2%) can hardly meet the demands of loading conditions for most flexible and stretchable device applications. In this paper, inspired from Kirigami, ancient Japanese art of paper cutting, we design and fabricate nanoscale Kirigami architectures of 2D layered MoS2 on a soft substrate of PDMS using a top-down fabrication process. Results show that the Kirigami structures significantly improve the reversible stretchability of flexible 2D MoS2 electronic devices, which is increased from 0.75% to ~15%. This increase in flexibility is originated from a combination of multi-dimensional deformation capabilities from the nanoscale Kirigami architectures consisting of in-plane stretching and out-of-plane deformation. We further discover a new fundamental relationship of electrical conductance and large strain in MoS2 Kirigami structures through both experimental work and finite element simulation. Results show that the electrical conductance of the stretchable MoS2 Kirigami is closely related to its different stages of structural evolutions under strain: e.g., elastic stretching; then a combination of elastic stretching and out-of-plane buckling; and finally stretching and structural damage. This method provides a new opportunity to fabricate highly flexible and stretchable sensors and actuators using different types of 2D materials.