The huge amounts of old and damaged tires spread worldwide has caused many complex environmental risks. The old tires have been converted to crumb rubber (CR) and tire recycled steel fiber (RSF) to facilitate their use. This study used CR to partially replace natural sand in reinforced (RC) columns. Externally bonded (EB) carbon-fiber-reinforced polymer (CFRP) laminates, welded wire mesh (WWM), and RSF were used to enhance the axial behavior of the tested columns to overcome the concrete deficiencies resulting from the inclusion of the CR instead of natural sand. Eighteen columns were prepared and tested to discuss the effects of strengthening type, CR content, RSF, and strengthening area on the axial behavior of the RC columns. Certain columns were internally reinforced with WWM, while others were externally strengthened with EB CFRP laminates. Partially or fully EB CFRP laminates were used to strengthen the columns. Moreover, one column was cast with NC and 0.2% RSF to investigate the role of RSF in confining the column. The results demonstrated a concrete strength reduction for the rubberized concrete (CRC) as the CR content increased. Conversely, the strengthened columns experienced higher load capacities than the corresponding un-strengthened ones cast with the same concrete mix. Moreover, adding 2% RSF to the NC mix could enhance the column capacity, although it decreased the concrete strength. Furthermore, using two CFRP layers increased the load capacity and ductility of the strengthened columns. The strengthened column cast with 50% CR showed the highest load efficiency (334.3% compared to the un-strengthened one).