Highly conductive and intrinsically stretchable electrodes are vital components of soft electronics such as stretchable transistors and circuits, sensors and actuators, light-emitting diode arrays, and energy harvesting devices. Many kinds of conducting nanomaterials with outstanding electrical and mechanical properties have been integrated with elastomers to produce stretchable conductive nanocomposites. Understanding the characteristics of these nanocomposites and assessing the feasibility of their fabrication are therefore critical for the development of high-performance stretchable conductors and electronic devices. We herein summarise the recent advances in stretchable conductors based on the percolation networks of nanoscale conductive fillers in elastomeric media. After discussing the material-, dimension-, and size-dependent properties of conductive fillers and their implications, we highlight various techniques that are used to reduce the contact resistance between the conductive filler materials. Furthermore, we categorize elastomer matrices with different stretchabilities and mechanical properties based on their polymeric chain structures. Then, we discuss the fabrication techniques of stretchable conductive nanocomposites toward their use in soft electronics. Finally, we provide representative examples of stretchable device applications and conclude the review with a brief outlook for future research.