Typically, the ash from incineration of paper sludge contains a high percentage of Ca in the form of anorthite (CaAl2Si2O8) and gehlenite (Ca2Al2SiO7). The Ca in the sludge originates from calcite that is included in paper as fillers. We applied acid leaching with HCl on the ash to reduce its Ca content. Zeolite was then synthesized from the leached ash through reaction with 2.5 M NaOH solution at 80 °C for 24 hours. The fraction of Ca and Al extracted from the ash correlates with the pH of the leachant. We determined the leachant pH (after 24 hours of leaching) associated with the Ca: Al:Si ratio in the leached ash that provided optimal production of zeolites with high cation-exchange capacity. During acid leaching, gehlenite dissolved out at higher pH than anorthite. In the case of pH > 5, both gehlenite and anorthite remained in the ash, and hydroxysodalite and LTA (Linde Type A) were synthesized in the product. In the case of pH = 1–5 in the leachant, gehlenite dissolved out but anorthite remained in the ash, and LTA and Na-P1 (zeolite-P) were produced. In the case of pH < 1, both gehlenite and anorthite dissolved out, and only Na-P1 was produced. The cation-exchange capacities of the products that contained hydroxysodalite, LTA, and Na-P1 were approximately 130, 200, and 120 cmol/kg, respectively. We conclude that acid leaching of paper sludge ash controls which of the three zeolite phases form, and that LTA and Na-P1 exhibit a higher cation-exchange capacity than hydroxysodalite. The most efficient production of zeolites with high cation-exchange capacity (about 220 cmol/kg) is obtained after leaching the sludge ash in solutions of around pH = 3. At this low pH, gehlenite has already dissolved out of the sludge ash, half the Ca content of the ash has been leached out, Si has not yet been leached, but Al has begun to be leached. After ash zeolitization, LTA coexists with Na-P1 in the product.