Embedding nanoparticles into an inert material like graphene is a viable option since hybrid materials are more capable than those based on pure nanoparticulates for the removal of toxic pollutants. This study reports for the first time on Cr(VI) removal capacity of novel starch stabilized nanozero valent iron-graphene composite (NZVI-Gn) under different pHs, contact time, and initial concentrations. Starch coated NZVI-Gn composite was developed through borohydrate reduction method. The structure and surface of the composite were characterized by scanning electron microscopy (SEM), X-ray diffraction spectroscopy (XRD), Fourier transform infrared spectroscopy (FTIR), Brunauer-Emmett-Teller (BET), and point of zero charge (pHpzc). The surface area and pHpzc of NZVI-Gn composite were reported as 525 m2 g−1 and 8.5, respectively. Highest Cr(VI) removal was achieved at pH 3, whereas 67.3% was removed within first few minutes and reached its equilibrium within 20 min obeying pseudo-second-order kinetic model, suggesting chemisorption as the rate limiting process. The partitioning of Cr(VI) at equilibrium is perfectly matched with Langmuir isotherm and maximum adsorption capacity of the NZVI-Gn composite is 143.28 mg g−1. Overall, these findings indicated that NZVI-Gn composite could be utilized as an efficient and magnetically separable adsorbent for removal of Cr(VI).