A simple co-precipitation method was employed in the synthesis of carbon-magnetic cobalt aluminum layered double hydroxide (Fe3O4/Co–Al LDH) and the obtained nano-structured material was further applied as an innovative adsorbent for the removal of two anionic dyes, namely Tartrazine (TA) and Indigo Carmine (IC). The synthesized nanosorbent was identified by scanning electron microscopy (SEM), energy-dispersive X-ray spectroscopy (EDX) and X-ray diffraction (XRD). In addition, Fe3O4/C/Co–Al LDH was magnetic and easily recovered by a small bar magnet after the sorption operation. The batch adsorption experiments were carried out to optimize different essential parameters such as contact time, initial dye concentration, solution pH, and adsorbent mass. Response surface methodology (RSM) involving central composite design (CCD) was also employed to obtain a suitable regression model for adsorption system and subsequently investigate the most influential parameters. Based on ANOVA results, all of the main parameters were significant. In particular, the initial dye concentrations and sorbent mass let to the largest variances on response values. The results showed the removal percentage of the dye increased by increase in the amount of the nanosorbent. In the contrary, the adsorption value of the nanosorbent for dye decreased by increasing the sorbent amounts. Moreover, the removal percentage and the adsorption value of the adsorbent decreased for each dye in the presence of another dye due to the competition between dyes for the available adsorbent surface area. Furthermore, the pseudo second-order model was used to describe the adsorption kinetics. The Langmuir isotherm model was the most suitable to fit the experimental data. The sorption capacities for TA and IC were obtained to be 52.3 and 61.7 mg/g, respectively