Highly improved catalytic reductive degradation of different organic dyes, in the presence of excess NaBH₄ over Au/CeO₂-TiO₂ nano-hybrid as the catalyst is reported in this study. CeO₂-TiO₂ nanocomposite was prepared by a facile co-precipitation method using ultra-high dilute aqueous solutions. Small amount of Au (only 1 wt%) was loaded onto the nanocomposite material by deposition-precipitation with urea (DPU) method to fabricate the ternary Au/CeO₂-TiO₂ nano-hybrid. The catalysts were characterized by the representative techniques like XRD, BET surface area, ICP-AES, UV-Vis diffuse reflectance spectroscopy, TEM and XPS. The Au/CeO₂-TiO₂ nano-hybrid along with NaBH₄ exhibited remarkable catalytic activities towards all the probed dyes, namely Methylene Blue, Methyl Orange, Congo Red, Rhodamine B and Malachite Green, with a degradation efficiency of ~100% in a short reaction time. The degradation reaction followed pseudo-first-order kinetics with respect to the concentration of the dye. Different parameters that affect the rate of the reaction are discussed. A plausible mechanism for methylene blue degradation has also been proposed.