Numerous efforts to prepare useful graphene-based nanocomposites have been made and important improvements achieved. In our studies, novel structured polyolefin-based thermoplastic elastomer, poly(ethylene-ter-1-hexene-ter-divinylbenzene) (PEHV) was designed and synthesized. And high quality graphene was manufactured via the exfoliation of graphite. PEHV/graphene nanocomposites were fabricated using solution casting method as the amount of graphene added. The morphologies of nanocomposites were observed using scanning electron microscopy. And density, mechanical properties and electrical properties were also measured. Electrical properties and mechanical properties were improved with the increase of graphene added in nanocomposites. It is expected that PEHV/graphene nanocomposites could be applied to lightweight EMI shielding materials.