Here, we report the piezoresistive behavior of ultra-soft, flexible and biocompatible carbon nanostructures (CNS) based polydimethylsiloxane (PDMS) nanocomposites under monotonic and cyclic loadings. CNS used here comprise MWCNTs that are branched, cross-linked and share common walls. The piezoresistive gauge factors obtained are 32, 15 and 7 for 0.05 wt. %, 0.1 wt. % and 0.2 wt. % of CNS loading, respectively. These gauge factors are higher than that of the conventional metallic sensors, which exhibit gauge factor of around 2. The nanocomposites remained conductive under cyclic loading and showed good piezoresistive sensitivity even after 100 cycles at both relatively low (5%) and high (30%) strain amplitudes. It is demonstrated that the strain sensing ability of the CNS/PDMS can be tuned, in terms of linearity and stretchability (from 25 % to 50 %) by varying the wt. % of CNS in PDMS matrix according to application requirements. To further elucidate the piezoresistive behavior of the CNS/PDMS composites, a simple theoretical model is developed relating the mechanical deformation to the piezoresistive response of the nanocomposites under uniaxial stretch. This study demonstrates the potential of CNS/PDMS nanocomposites in personal health monitoring owing to its strain-sensing capability.