The study presents experimental investigation to assess influence of cryogenic treatment of electrodes on machinability in powder-mixed electrical discharge machining (PMEDM). Response surface methodology is used to extract maximum process related information with less number of experimental runs. The machining characteristics of the process are evaluated in terms of material removal rate (MRR), electrode wear ratio (EWR) and surface roughness which are function of machining parameters viz. open circuit voltage, discharge current, pulse-on-time, duty factor, concentration of fine graphite powder and cryogenically treated work tool pair. The study reveals that discharge current, pulse-on-time, concentration of powder and work-tool pair exhibit significant effect on all the performance measures. It is also observed that treatment to both the electrodes results in more beneficial in comparison to treatment of either the tool or work piece. Finally, a novel multi-objective particle swarm optimisation algorithm (MOPSO) has been proposed in order to achieve optimal Pareto front. Copyright © 2017 Inderscience Enterprises Ltd.