In this paper, a new method is presented to determine the optimal setting of distance relays using probabilistic modeling of the affected uncertainties. Due to model of uncertainties, the corresponding density functions of each uncertainty are presented. Then, using Monte Carlo simulation, the probability distribution of the impedance seen by the distance relay is obtained. The three zones of distance relay need to be set in a way that the relay operates correctly for an internal fault of the protection zone (sensitivity), and it does not operate for an external fault of the protection zone (selectivity). According to this, the probabilistic indices of sensitivity and selectivity are defined independently for each zone of the distance relay. In the following, different scenarios are proposed to maximize the selectivity or sensitivity indices.Finally, due to importance of selectivity in compare to sensitivity, the scenario of maximized sensitivity with perfect selectivity is proposed.According to this scenario, the problem of determining optimum setting of distance relay for each zone is defined as an optimization problem with the objective of maximizing the probability of sensitivity and with the constraint of perfect selectivity.Since the proposed formulation is nonlinear, Genetic algorithm is used to solve this problem. The proposed method is applied to the IEEE 39 bus test system and the advantages of the proposed formulation for each zone of the distance relay are presented.