The synthesis of FeTiO3-Ni(Ni80Fe20) core-shell nanostructures by a two-step method (sol-gel and DC electrodeposition) has been demonstrated. XRD analysis confirms the rhombohedral crystal structure of FeTiO3(FTO) with space group R3[combining macron]. Transmission electron microscopy clearly depicts better morphology of nanostructures with shell thicknesses of ∼25 nm. Room temperature magnetic measurements showed significant enhancement of magnetic anisotropy for the permalloy (Ni80Fe20)-FTO over Ni-FTO core-shell nanostructures. Low temperature magnetic measurements of permalloy-FeTiO3 core-shell structure indicated a strong exchange bias mechanism with magnetic coercivity below the antiferromagnetic Neel temperature (TN = 59 K). The exchange bias is attributed to the alignment of magnetic moments in the antiferromagnetic material at low temperature. Our scheme opens a path towards optimum automotive systems and wireless communications wherein broader bandwidths and smaller sizes are required.