Photocatalysts based on graphitic carbon nitride (g-C3N4) attracted considerable attention due to their efficiency in hydrogen production and decomposition of organic pollutants in aqueous solutions. In this work, a new approach to synthesis of g-C3N4-based heterostructures with improved photocatalytic properties was proposed. The properties of two different CdZnS/g-C3N4 and ZnIn2S4/g-C3N4 heterostructures synthesized and studied in the same conditions were compared. Pure g-C3N4 photocatalysts as well as CdZnS/g-C3N4 and ZnIn2S4/g-C3N4 heterostructures were synthesized using a one-pot method by calcining the mixture of the initial components. Photocatalytic properties of the synthesized substances were evaluated in a model reaction of rhodamine B decomposition induced by visible light. It was shown that ultrasonic treatment in the presence of a nonionic surfactant enhances the photocatalytic activity of g-C3N4 structures as a result of a higher photocatalyst dispersity. The electronic structures of the CdZnS/g-C3N4 and ZnIn2S4/g-C3N4 heterostructures were analyzed in detail. The photocatalytic activity of heterostructures was found to be 2–3-fold higher as compared with an unmodified g-C3N4 due to formation of a type II heterojunction and Z-scheme structures. Decomposition of rhodamine B occurred mostly via formation of active oxygen radicals by irradiation.