Iron deficiencies continue to cause significant health problems in vulnerable populations. A good strategy to combat mineral deficiency includes fortification with iron-binding peptides. This research aims to determine the optimal conditions to hydrolyze red tilapia viscera (RTV) using Alcalase 2.4 L and recovery of iron-binding protein hydrolysate. The result showed that under the optimal hydrolysis condition including pH 10, 60 °C, E/S ratio of 0.306 U/g protein, and substrate concentration of 8 g protein/L, the obtained hydrolysate with 42.5% degree of hydrolysis (RTVH-B), displayed the maximal iron-binding capacity of 67.1 ± 1.9%. Peptide fractionation was performed using ultrafiltration and the <1 kDa fraction (FRTVH-V) expressed the highest iron-binding capacity of 95.8 ± 1.5%. Iron content of RTVH-B and its fraction was assessed, whereas iron uptake was measured indirectly as ferritin synthesis in a Caco-2 cell model and the result showed that bioavailability of bound minerals from protein complexes was significantly higher (p < 0.05) than iron salt in its free form, increased 4.7 times for the Fe2+–RTVH-B complex. This research suggests a potential application of RTVH-B as dietary supplements to improve iron absorption.