Thermal interface material (TIM) is a key component to dissipate the accumulated heat in the majority of power electronic systems. In this work, a facile and solid-state ball-milling method is adopted for the solvent-free reduction of exfoliated graphite nanoplatelets (EGNs) into high-quality ball-milled exfoliated graphite nanoplatelet (BMEGN) fillers. In addition, BMEGN fillers are embedded and uniformly dispersed with polydimethylsiloxane (PDMS) matrix to make a highly stretchable BMEGN-embedded PDMS-TIMs (BMEGN/PDMS) with strongly enhanced thermal conductivity. Furthermore, material characterizations were thoroughly investigated using scanning electron microscopy, transmission electron microscope, Raman spectroscopy, thermogravimetric analysis, and x-ray diffraction. Improvements in the thermal conductivity of TIMs by adding BMEGN were compared, the thermal conductivity was observed for BMEGN fillers with 0- to 48-h ball-milling time, and an enhanced in-plane thermal conductivity of 15.04 to 16.91 W/mK and through-plane thermal conductivity of 1.03 to 1.19 W/mK can be experimentally measured. A strong anisotropy was observed in the range of 14.60 (BMEGN12h/PDMS) to 14.21 (BMEGN48h/PDMS). The results reveal that the ball-milled graphene filler network with branched morphology can effectively provide the synergetic effect of a thermally conductive pathway via diffusion of phonon vibration in flexible composites. The combination of thermal conductivity and thermal stability may facilitate the applications in thermal management.