Lightweight aggregate (LWA) production with sewage sludge and municipal solid waste incineration (MSWI) fly ash is an effective approach for waste disposal. This study investigated the stability of heavy metals in LWA made from sewage sludge and MSWI fly ash. Leaching tests were conducted to find out the effects of MSWI fly ash/sewage sludge (MSWI FA/SS) ratio, sintering temperature and sintering time. It was found that with the increase of MSWI FA/SS ratio, leaching rates of all heavy metals firstly decreased and then increased, indicating the optimal ratio of MSWI fly ash/sewage sludge was 2:8. With the increase of sintering temperature and sintering time, the heavy metal solidifying efficiencies were strongly enhanced by crystallization and chemical incorporations within the aluminosilicate or silicate frameworks during the sintering process. However, taking cost-savings and lower energy consumption into account, 1100 °C and 8 min were selected as the optimal parameters for LWA sample- containing sludge production. Furthermore, heavy metal leaching concentrations under these optimal LWA production parameters were found to be in the range of China’s regulatory requirements. It is concluded that heavy metals can be properly stabilized in LWA samples containing sludge and cannot be easily released into the environment again to cause secondary pollution.