In this study, a novel nanoscale iron oxide (FeOx) modified carbon nanotubes composite (FeOx@CNTs) was synthesized through a combined ball milling–hydrothermal two-step method and tested for aqueous Sb(III) removal efficiency and mechanisms. FeOx nanoparticles was successfully loaded on the surface of CNTs through functional groups such as hydroxyl (–OH), C–H, and C–O to enhance the removal efficiency of Sb(III) through adsorption and surface complexation. At a dosage of 0.02 g, a FeCl3·6H2O-to-CNTs mass ratio of 3:1, and an initial solution pH of 6.3, the amount of Sb(III) removed by the prepared FeOx@CNTs reached 172 mg/g, which was 42.9 times higher than that of the pristine CNTs (4.01 mg/g). Chemical adsorption and oxidation were the main removal mechanisms. At the equilibrium Sb(III) concentration of 6.08 mg/L, 6.56% of initial Sb(III) was adsorbed onto the surface of FeOx@CNTs, and 81.3% of initial Sb(III) was oxidized to Sb(V) with lower toxicity. The pseudo-second-order kinetic model could better describe the adsorption of Sb(III) onto the FeOx@CNTs composite, indicating that adsorption was mainly controlled by chemical sorption. In the adsorption isotherm equation, the Redlich–Peterson model provided a better fit of Sb(III) adsorption onto the FeOx@CNTs composite than the Langmuir and Freundlich models, which further indicated that the adsorption process was a hybrid removal process dominated by chemical sorption. The presence of CO3 2− slightly promoted the removal of Sb(III) from aqueous solution. The synthesized composite was magnetic and could be easily separated from the solution by an external magnetic field at the end of the sorption experiment. Based on these findings, the FeOx@CNTs nanocomposite is expected to provide an environmentally-friendly adsorbent with a strong sorption capacity for remediating Sb(III) in water environments.