A simple but effective method of fabricating superhydrophobic paper with excellent moisture resistance was developed by precipitating carnauba wax onto the surface of cellulose fibers using a phase separation method. Response surface methodology (RSM) was used to optimize the effects of the preparation variables on the water contact angle (WCA) of the paper surface. The four independent variables were carnauba wax concentration, immersion time, coagulation bath ratio (water/ethanol), and coagulation bath time. The optimal treatment conditions were as follows: wax concentration, 3.78% (wax/chloroform, w/v); immersion time, 1.46 h; coagulation bath ratio, 13/87 (water/ethanol, v/v); and coagulation bath time, 2.63 h. Under these conditions, the experimental WCA reached 152.7°, which agreed closely with the predicted value of 154.1°. The surface morphology of the superhydrophobic paper was characterized by scanning electron microscopy (SEM) and atomic force microscopy (AFM), and the images showed that cluster-like carnauba wax aggregation completely covered the fiber surface, resulting in increased roughness. Moreover, the moisture resistance of the obtained superhydrophobic paper was evaluated. The results demonstrated that under high relative humidity conditions, the moisture resistance of the superhydrophobic paper significantly improved, and its tensile strength remained high.