We designed novel Cd-doped WO3 (CWC) and Cd-doped WO3@g-C3N4 (CWCC) heterostructure nanocomposites using a facile process and used them to remove pollutants from wastewater under visible light (VL). The g-C3N4 was designed in the form of a disk (CNDs) to facilitate the formation of CWCC composite. The photocatalytic efficiency of the CWCC was studied via the decomposition of methylene blue (MB), rhodamine 6G (Rh 6G), methyl red (MR), and methyl orange (MO). Outstanding photocatalytic performance of 95.98% was achieved within 80 min for MB. The efficiency of CWCC was 670%, 350%, 220%, 130%, and 121% greater than that of the blank, CNDs, pristine WO3, CWC, and WO3/g-C3N4 nanodisks, respectively. Under the same experimental conditions, the photocatalytic performance of CWCC was 82.22%, 77.51%, and 42.90% towards Rh 6G, MR, and MO, respectively. The increased catalytic efficiency of CWCC was attributed to a lowering of the bandgap and a favorable potential-energy location of the valence band and conduction band for photocatalysis by Cd doping and/or the formation of a heterojunction between the CWC and CNDs compositing with CNDs. The presence of a heterojunction enhanced the charge transfer and diminished the recombination of charge carriers. Two probable mechanisms are discussed.