Iron oxide-based nanostructures receive significant attention as an efficient adsorbent for organic dyes removal. The removal properties have strong dependency on the stoichiometry, phases, reactive edges, defect states etc present in the iron-oxides nanostructures. Herein, iron oxide/carbon composite with well-defined heterophased grain boundaries is synthesized by simple precipitation method and followed by calcination. The local structure, spin dynamics and magnetic properties of heterophased iron oxides/carbon composite are thoroughly investigated to explore its cationic and anionic dye removal capability. To validate the effectivity of the presence of heterogeneous grain boundaries, iron oxide/carbon nanocomposite with homogeneous grain boundaries is also examined. It was found that the hetero-phased iron oxide/carbon showed removal capacity of 35.45 mg g-1 and 45.84 mg g-1 for cationic (Crystal Violet) and anionic (Congo Red) dyes, respectively as compared to that of as-synthesised imidazole-capped superparamagnetic {\alpha}-Fe2O3 (25.11 mg g-1 and 40.44 mg g-1, respectively) and homophased iron oxide/carbon nanocomposite (9.41 mg g-1 and 5.43 mg g-1, respectively). The plausible mechanism on the local structural evolution of the heterophase in the course of calcination and increase of the removal capacity is discussed. A detailed dye adsorption investigation is presented including the adsorption kinetic study. The pseudo-second order kinetic model is found to be an appropriate one and suggests that the chemisorption is dominant factor leading to adsorption of dyes. Whereas Weber-Morris model indicate the strong influence of boundary layers of nanocomposite on the adsorption process.