Urumqi, the administrative center of Xinjiang, suffers from severe atmospheric aerosol pollution; however, no study has comprehensively analyzed the local constituents and sources of fine particulate matter (PM2.5). The characteristics of PM2.5 in Urumqi were observed the first winter (2012–2013) after natural gas replaced coal as an energy source. Enrichment factors, backward trajectories, the potential source contribution function (PSCF) model, and positive matrix factorization (PMF) were used to identify the source area and categories. The results showed a mean concentration of 197.40 µg m–3 for the PM2.5, which significantly decreased after the conversion from coal to natural gas. Although the concentration of NO3– increased post-conversion, the SO42– and Cl– decreased by 42.54% and 32.93%, respectively. The water-soluble ions (WSIs) mainly consisted of NH4HSO4, CaSO4, MgSO4, Ca(NO3)2, Mg(NO3)2, and KCl. Elements such as Pb, Cr, and As decreased following the fuel switch. The organic carbon and elemental carbon were strongly correlated, and the mean concentration of the secondary organic carbon was 18.90 µg m–3. Pyr, Chr, BbF, BkF, IcdP, and BghiP were the most prevalent individual polycyclic aromatic hydrocarbons, and BaP exceeded health-based guidelines. The results from trajectory clustering and PSCF modeling suggested that emissions from both the city and its surroundings, as well as the valley-and-basin topography, may be responsible for the heavy PM2.5 pollution in southern Urumqi. PMF identified five primary sources: secondary formation, biomass and waste burning, vehicle emissions, crustal minerals, and industrial pollution and coal combustion.