The removal of arsenic from water by adsorption is currently hindered by the elevated cost of conventional adsorbent materials. To overcome this limit, an innovative iron-coated adsorbent was produced by hydrothermal carbonization (170 °C, 30 min) of olive pomace, an inexpensive byproduct of the olive oil production. Hydrothermal carbonization experiments were performed starting from olive pomace dispersions in solutions with acidic, neutral and alkaline pH, in presence and absence of FeCl3. Acidic conditions improved the carbonization, ensuring reduced H/C and O/C ratios, and increased the adsorbent stability. However, acidic pH yielded unsatisfactory iron coating, with only 32% of the iron dissolved in the initial solution transferred to the produced hydrochar. Under alkaline pH, 96% of the iron in the feedwater was, in contrast, stably dispersed over the hydrochar surface, giving the highest maximum arsenic adsorption capacity (4.1 mg/g). However, alkaline pH promoted biomass hydrolysis, causing the loss of 60% and 87% of the total C and N, respectively, and reducing the stability of the produced hydrochar. A two-stage process was tested to overcome these issues, including hydrothermal carbonization under acidic pH with FeCl3, followed by the addition of NaOH. This process prevented biomass hydrolysis yielding a stable hydrochar. However, as compared to the one-stage alkaline synthesis, the two-stage process produced an hydrochar with reduced arsenic adsorption capacity (1.4 mg/g), indicating that biomass hydrolysis could positively influence hydrochar adsorption characteristics, possibly by increasing the specific surface area. Indications are then provided on how to optimize the two-stage process in order to produce a hydrochar with both satisfactory stability and arsenic adsorption capacity.