Asphaltene, an otherwise undesirable waste from the oil industry, was refined from heavy oil fractions and processed under different conditions to obtain carbonaceous materials with large surface area to be used in supercapacitors. Carbon electrode materials were successfully fabricated by a facile thermal process using melamine foam as template and KOH activation. The effect of different synthesis parameters on morphological and electrochemical performance is reported, namely, the weight ratio KOH:asphaltene, homogenization time, temperature and duration of thermal treatment. The materials were characterized by Raman, BET, SEM/EDS, and XPS; and their performance, in terms of specific capacitance and stability, was assessed by different electrochemical methodologies. Results show that an optimized material, using specific capacitance and active material recovery as optimization targets, was obtained by using a KOH: asphaltene weight ratio of (3:1), homogenization time of 1 h and thermal treatment at 700°C for 0.5 h. This material had a specific energy of 8.6 W h kg−1, specific power of 645 W kg−1 and a specific capacitance of 112 F g−1 at 0.4 A g−1 current density.