A new alloy design methodology is presented for the identification of alloy compositions, which exhibit process windows (PWs) satisfying specific design objectives and optimized for overall performance. The methodology is applied to the design of medium-Mn steels containing Al and/or Ni. By implementing computational alloy thermodynamics, a large composition space was investigated systematically to map the fraction and stability of retained austenite as a function of intercritical annealing temperature. Alloys exhibiting PWs, i.e., an intercritical annealing range, which when applied satisfies the given design objectives, were identified. A multi-objective optimization method, involving Pareto optimality, was then applied to identify a list of optimum alloy compositions, which maximized retained austenite amount and stability, as well as intercritical annealing temperature, while minimized overall alloy content. A heuristic approach was finally employed in order to rank the optimum alloys. The methodology provided a final short list of alloy compositions and associated PWs ranked according to their overall performance. The proposed methodology could be the first step in the process of computational alloy design of medium-Mn steels or other alloy systems.