We report the discovery of a Broad Absorption Line (BAL) of \sim 10^4 km s-1 in width in the previously known BL Lac object PKS 0138-097, which we tentatively identified as a Mg II BAL. This is the first detection of a BAL, which is sometimes seen in powerful quasars with high accretion rates, in a BL Lac object. The BAL was clearly detected in its spectra of two epochs at a high luminosity state taken in the Sloan Digital Sky Survey (SDSS), while it disappeared in three SDSS spectra taken at a low luminosity state. The BAL and its variability pattern was also found in its historical multi-epoch spectra in the literature, but has been overlooked previously. In its high resolution radio maps, PKS 0138-097 shows a core plus an one-sided parsec-scale jet. The BAL variability can be interpreted as follows: The optical emission is dominated by the core in a high state and by the jet in a low state, and the BAL material is located between the core and jet so that the BAL appears only when the core is shining. Our discovery suggests that outflows may also be produced in active galactic nuclei at a low accreting state.