The accumulation of organic pollutants and solid waste is one of the major environmental challenges faced globally. Establishing an efficient recycling system for solid waste and designing cost-effective, high-performance photocatalysts are urgent tasks for the removal of organic pollutants from water. This study utilizes coal gangue as the precursor to synthesize a coal gangue-based phosphorus-silicon-aluminum molecular sieve (SAPO-5) via hydrothermal synthesis. The resulting material was then composited with bismuth oxybromide (BiOBr) to form a novel BiOBr/coal gangue-based SAPO-5 nanocomposite. When the mass ratio of BiOBr to coal gangue-based SAPO-5 molecular sieve is 0.3, the synthesized nanocomposite exhibits excellent adsorption and photocatalytic performance for the removal of methylene blue, achieving a removal rate of 97.8% and the mineralization rate of 57.4% within 30 min. The superior performance can be attributed to the optimal pore size, rapid charge transfer rate, and high photogenerated charge density of the BiOBr/coal gangue-based SAPO-5 nanocomposite. The novel BiOBr/coal gangue-based SAPO-5 molecular sieve nanocomposite catalyst presents a new approach for the harmless treatment of organic dye wastewater and the high-value utilization of coal gangue.