A novel magnetically recoverable Au nanocatalyst was fabricated by spontaneous green synthesis of Au nanoparticles on the surface of gum arabic-modified Fe3O4 nanoparticles. A layer of Au nanoparticles with thickness of about 2 nm was deposited on the surface of gum arabic-modified Fe3O4 nanoparticles, because gum arabic acted as a reducing agent and a stabilizing agent simultaneously. The resultant magnetically recoverable Au nanocatalyst exhibited good catalytic activity for the reduction of 4-nitrophenol with sodium borohydride. The rate constants evaluated in terms of pseudo-first-order kinetic model increased with increase in the amount of Au nanocatalyst or decrease in the initial concentration of 4-nitrophenol. The kinetic data suggested that this catalytic reaction was diffusion-controlled, owing to the presence of gum arabic layer. In addition, this nanocatalyst exhibited good stability. Its activity had no significant decrease after five recycles. This work is useful for the development and application of magnetically recoverable Au nanocatalyst on the basis of green chemistry principles.