With recent advancements in novel composite nanomaterials and microstructures, wearable electronic devices, particularly flexible and stretchable strain sensors, are receiving significant attention. This article reviews recent developments in composite-based flexible and stretchable strain sensors for wearable applications, such as those in healthcare and human motion detection, sports and physical training, soft robotics, and smart textiles. Material compositions and structures are categorically discussed based on their respective sensing mechanisms and novel structural interfaces. Four major categories of composites are reviewed in detail: carbon materials, nanowires (NWs) and nanoparticles (NPs), liquids, and newly emerging bio-hybrid nanocomposites. Parametric evaluations are conducted on the performance characteristics of these stretchable sensors, including those related to their respective composite interfaces. Potential applications of these high-performance strain sensors are discussed, along with the key technological challenges and future trends for improving sensor fabrication and performance.