A random coding method for a Brillouin optical time domain reflectometer (BOTDR) fiber sensor is proposed. In this method, a series of pulses modulated by random code are injected into the optical fiber to enhance the signal-to-noise ratio (SNR) and further improve the measurement accuracy. Random coding method allows the sensing range to be extended to several tens of kilometers while maintaining meter-scale spatial resolution and lower detection peak power, without modifying the conventional configuration of BOTDR. The decoding principle and the coding gain of random coding method are analyzed and simulated. We experimentally implement the method and evaluate its influence on the performance optimization of BOTDR. Compared with the single pulse with peak power of 10 mW, the measured BFS uncertainty over 4.93 km sensing fiber is reduced from 5.34 MHz to 0.38 MHz when 512-bit random coding pulses with the same peak power are utilized. The experimental results show that the coding gain of 11.93 dB is obtained by 512-bit random coding. Benefitting from the SNR enhancement, the sensing range is extended from 4.93 km to 64.76 km within a root-mean-square error (RMSE) of 3 MHz, when the pulse peak power is only 10 mW and the spatial resolution is 2 m.