This paper proposes a multi-year multi-objective planning algorithm for enabling distribution networks to accommodate high penetrations of plug-in electric vehicles (PEVs) in conjunction with renewable distributed generation (DG). The proposed algorithm includes consideration of uncertainties and will help local distribution companies (LDC) better assess the expected impacts of PEVs on their networks and on proposed renewable DG connections. The goal of the proposed algorithm is to minimize greenhouse gas emissions and system costs during the planning horizon. An approach based on a non-dominated sorting genetic algorithm (NDSGA) is utilized to solve the planning problem of determining the optimal level of PEV penetration as well as the location, size, and year of installation of renewable DG units. The planning problem is defined in terms of multi-objective mixed integer nonlinear programming. The outcomes of the planning problem represent the Pareto frontier, which describes the optimal system solutions, from which the LDC can choose the system operating point, based on its preferences.