Random polarization control in Golay-coded Brillouin optical time domain analysis (BOTDA) fiber sensors can be used to mitigate the deterioration in the signal-to-noise ratio caused by the strong pulling effect of polarization. However, a relatively strong polarization random noise (PRN) is induced, which may reduce the measurement accuracy of the sensing signal. In this study, the effect of PRN on the sensing signal was confirmed through simulation analysis and experimental verification. Furthermore, Brillouin phase shift was used to suppress PRN. Experimental results show that the sensing accuracy is enhanced threefold using the proposed method.