The decarbonization of power systems is among the primary actions to fight air pollution and climate change. In this study, we evaluate the costs of a gradual transition towards a new power system in which the oldest coal plants are replaced with low-carbon power plants. We developed the Wind Energy Integration Cost Advisor Model (WEICAM) to analyze different strategies for this energy transition and determine the most cost-effective roadmap, with and without externalities. The test case is the PJM Interconnection, one of the power systems in the United States with the largest fraction of coal. Different strategies to replace coal plants are evaluated: 1) installing only new, high-efficiency, natural-gas combined-cycle plants (control case), 2) installing new wind farms in combination with natural-gas combined-cycle plants used as spinning reserves (wind case), and 3) same as the wind case but boosting up the production of existing baseload plants that work with a capacity factor between 50% and 60%–80% before installing new wind farms. All three strategies have similar costs (∼54 $/MWh), but the latter is slightly more cost-effective, with a total of 19 GW of coal capacity decommissioned and an increase in the levelized cost of electricity from 49.1 to 53.6 $/MWh (without externalities). In addition, selecting the windiest sites – even far away from the PJM region – is cheaper than selecting local but less windy sites. When externalities due to human health and environmental pollution are accounted for, the two wind-based strategies become the most advantageous, reducing the levelized cost below 104 $/MWh from the initial 110 $/MWh. We conclude that adding new wind farms from the windiest locations, accompanied by a better management of existing plants and a small addition of new natural-gas reserve capacity, is the most economic and the most environmentally responsible pathway to replace retiring coal-fired power plants in PJM.