In the present study, a novel superparamagnetic nanocomposite composed of magnetite as the core and zeolite coated by glutaraldehyde-crosslinked chitosan as the shell has been successfully synthesized. The synthesis steps include coating silica on the surface of magnetite nanoparticles and conversion of the silica layer into a zeolite layer, coating of chitosan on the surface of the zeolite, and cross-linking reaction of chitosan using glutaraldehyde. The X-ray diffractogram has proven that the magnetite nanoparticles formed on the nanocomposite have a cubic structure. The formation of the minerals mordenite, clinoptilolite, and quartz on the magnetite surface is also confirmed. Infrared spectral analysis has revealed the existence of Fe–O–Si and Fe–O–Al bonds between magnetite and zeolite, and C=N bonds between chitosan and glutaraldehyde. The TEM image clearly shows that the resulting nanocomposite consists of zeolite-coated magnetite nanoparticles, which are incorporated in a glutaraldehyde crosslinked chitosan gel system. Measurements with ImageJ software suggest that the diameter of the composite is in the range of 20–75 nm, with an average diameter of 34.06 nm. Magnetic studies indicate that the nanocomposite is superparamagnetic with a saturation magnetization of 27.5 emu/g. Since the magnetite nanoparticles is positioned in the core of the composite, it is well protected from oxidation and therefore it is expected to have high magnetic stability. This magnetically separable nanocomposite is quite interesting and may be applied in the adsorption of heavy metal ions and cationic dyes from aquatic medium.