The sensitivity of a sensor to strain or the temperature variations due to distributed Brillouin scattering are partially related to the type of fibers used and the Brillouin scattering induced effective index. In this paper, a highly nonlinear fiber that can generate a higher Brillouin scattering signal is compared to a standard single mode fiber in a short-time-Fourier-transform Brillouin optical time domain reflectometer (STFT-BOTDR). The results show that much higher signal to noise ratios of the Brillouin scattering spectrum and smaller frequency uncertainties in the sensing measurement can be achieved in the highly nonlinear fiber for comparable launched powers. With a measurement speed of 4 Hz, the frequency uncertainty can be 0.43 MHz, corresponding to 10 με in strain or 0.43°C in temperature uncertainty for the highly nonlinear fiber. In contrast, for the standard single mode fiber case, the value would increase to about 1.02 MHz (25 με or 1.02°C), demonstrating the advantage of the highly nonlinear fiber for distributed strain/temperature sensing.