A step-index tellurite optical fiber with loss ∼0.02 dB/m at ∼1545 nm was fabricated based on TeO2-Bi2O3-ZnO-Na2O glass. With a nanosecond laser operated at ∼1545 nmas the pump source, second-harmonic generation (SHG) was observed in the 2.5 m tellurite fiber with conversion efficiency up to ∼1.15% at 20 mW, which, to the best of our knowledge, is the highest for non-silica optical fibers. The experimental phenomenon can be explained by the χ(2)-induced model of nonlinear polarization at the core-cladding interface. Furthermore, it can also be explained by a χ(3)-induced model via the four-wave-mixing effect, where a quasi-SH signal and a millimeter wave were generated simultaneously. This new model may help shed light on the physical mechanism of SHG in optical fibers.