Visible active binary g-C3N4 (CN) embedded NaTaO3 (NTO) photocatalyst were synthesized via hydrothermal method, followed by annealing. The phase formation and surface morphology of the NTO-CN heterostructure illustrated the formation of monoclinic NaTaO3 crystallite and layered g-C3N4. The light-response properties of NTO-CN heterostructure were significantly broadened in the visible spectrum. The elemental composition, binding energy, oxidation states of the constituent elements and surface adsorption of the synthesized materials were characterized. The percentage of degradation of RhB dye employing NTO-CN heterostructure photocatalyst was computed to be 92.3%. This value was 1.66 times and 1.49 times greater than NaTaO3 and g-C3N4 respectively. Pseudo first order rate constant value for NTO-CN heterostructure photocatalyst was calculated to be 0.0288 min-1. This value was 3.43 times and 2.82 times greater than NaTaO3 and g-C3N4 respectively. Photocatalytic water splitting experiment was performed and amount of hydrogen evolved for 5 hrs was measured to be 1104 μmol/g for NTO-CN, which was greater by a factor of 2.32 and 1.43 as that of NaTaO3 and g-C3N4 respectively. In comparison to bare g-C3N4 and NaTaO3, the NTO-CN heterostructure photocatalyst demonstrated maximized photocatalytic performance. This study analyzed advancing practical application of NaTaO3 photocatalysts by forming heterostructure with g-C3N4.