Studies of negative magnetoresistance in novel materials have recently been in the forefront of spintronic research. Here, we report an experimental observation of the temperature dependent negative magnetoresistance in BiTe topological insulator (TI) nanowires at ultralow temperatures (20 mK). We find a crossover from negative to positive magnetoresistance while increasing temperature under longitudinal magnetic field. We observe a large negative magnetoresistance which reaches -22% at 8 T. The interplay between negative and positive magnetoresistance can be understood in terms of the competition between dephasing and spin-orbit scattering time scales. Based on the first-principles calculations within a density functional theory framework, we demonstrate that disorder (substitutional) by Ga ion milling process, which is used to fabricate nanowires, induces local magnetic moments in BiTe crystal that can lead to spin-dependent scattering of surface and bulk electrons. These experimental findings show a significant advance in the nanoscale spintronics applications based on longitudinal magnetoresistance in TIs. Our experimental results of large negative longitudinal magnetoresistance in 3D TIs further indicate that axial anomaly is a universal phenomenon in generic 3D metals.