Thermoplastic elastomeric nanocomposites have a wide range of applications in the automotive, medical, electronics, and energy sectors. Good mechanical and fracture performances are typically needed to reach the desired properties for the applications. In this study, tensile and fracture properties of exfoliated graphite (EG) filled PP toughened with ethylene-vinyl acetate (EVA) are examined. Accordingly, four levels of EVA (0, 10, 20, and 30 wt.%) and EG (0, 1, 3, and 5 wt.%) are utilized. The full factorial design is employed to explain the effect of independent parameters and their interaction on responses. The essential work of fracture (EWF) methodology is also employed to investigate the fracture behavior of the blend nanocomposites. By increasing EVA, the elongation at break and non-EWF are increased by 188% and 75%, in succession. Moreover, the tensile modulus is improved up to 11% by increasing EG. The compound with 10 wt.% EVA and 1 wt.% EG has the best toughness-strength-stiffness balance based on the optimization results.