A novel Brillouin random fiber laser (BRFL) with the random grating-based Fabry-Perot (FP) resonator is proposed and demonstrated. Significantly enhanced random feedback from the femtosecond laser-fabricated random grating overwhelms the Rayleigh backscattering, which leads to efficient Brillouin gain for the lasing modes and reduced lasing threshold. Compared to the intensity and frequency noises of the Rayleigh feedback resonator, those of the proposed random laser are effectively suppressed due to the reduced resonating modes and mode competition resulting from the random grating-formed filters. Using the heterodyne technique, the linewidth of the coherent random lasing spike is measured to be ∼45.8 Hz.