Titanium alloys, especially Ti-6Al-4V, which is considered a difficult-to-cut material, bears numerous applications in aerospace and biomedical sectors. The criticality of the accurate formation of the machined cavity for the said applications and properties of Ti-6Al-4V accentuated the use of electric discharge machining (EDM). However, the issues of lower material removal rate (MRR) and tool wear (TWR) discouraged the use of EDM. These inherent issues hold a pivotal role regarding the sustainable machining of Ti-alloy. Therefore, in this research the potentiality of kerosene-based dielectric, having graphene nanoparticles, is comprehensively examined for the sustainable EDM of Ti-6Al-4V, which was not focused upon yet. Experimentation was performed under Taguchi’s design (L18) with three types of electrodes, namely Aluminum, Brass and Copper. In total, 36 experiments were conducted, of which 18 were with graphene-mixed dielectric and the remaining were with kerosene. Experimental results reveal that the brass electrode with negative tool polarity yields higher MRR for both types of dielectrics. The maximum MRR (7.602 mm3/min) achieved with graphene mixed dielectric is 64.5% greater as compared to that obtained with kerosene (4.621 mm3/min). Moreover, the minimum TWR obtained for graphene-based dielectric, i.e., 0.17 mg/min is approximately 1.5 times less than that achieved with kerosene.