In this paper a new method is presented for setting the quadrilateral characteristic of distance relay, considering sensitivity and selectivity criteria for protection zones. The main protection scheme used for transmission lines is distance protection. Due to the uncertainty of the effective parameters on relay’s estimated impedance the issue of optimal setting of the relay arises. In the proposed method of the paper, in addition to the variations of fault resistance, pre-fault load flow and measurement errors, the probabilistic changes of system topology and their corresponding effects are also considered. Optimal characteristic search is applied using Genetic Algorithm (GA). The obtained results for new method demonstrates a noticeable increase in the accuracy of this scheme compared to the conventional ones.