Reduced graphene oxide (rGO)-coated microfibers (GCMs) have been developed through a straightforward synthesis by soaking microfiber cloths in graphene oxide (GO) aqueous dispersions and followed by reduction with hydrazine vapors in autoclave at 80 °C. The produced GCMs show high hydrophobicity and oleophilicity, which can be used to recover crude oil from oil-in-water mixtures. The microscopic structures have been analyzed under optical microscopy and scanning electron microscopy; confirming the presence of rGO on the microfibers’ surface. Thermal gravimetric analysis measurements showed that GCMs are stable up to 300 °C. Raman spectroscopy indicated a strong quenching of the polymers’ peaks in GCMs and the appearance of graphene’s D and G peaks due to the rGO coating. The maximum uptake capacity of the GCMs is 6.78 g of oil per gram of material with a reduction of 13.5% after 10 adsorption-desorption cycles. Removals of 97.90% and 87.58% of crude oil have been achieved after a single application of GCMs in 1% (v/v) oil-water and oil-artificial seawater mixtures respectively. Oil concentrations below 35 ppm have been reached after the second and the fifth application of GCMs in oil-water and oil-artificial seawater mixtures respectively. The adhesion strength of the rGO coating has been assessed by different means such as sonication and vigorous mixing in water; the highest amount of rGO released in water was 8.3 ppm after 30 minutes of sonication. These properties suggest that GCMs can be used, as prepared or combined in filter devices, as a possible oil recovery method in case of oil spills.