Recently, the adoption of recycled concrete instead of normal concrete as infill material in tubular stainless steel members has received great attention from researchers regarding environmental improvement. However, the flexural behavior of recycled concrete-filled stainless steel tube (RCFSST) beams that have been repaired/strengthened using carbon fiber-reinforced polymer (CFRP) sheets via a partial-wrapping scheme has not yet been investigated, and is required for a variety of reasons, as with any conventional structural member. Therefore, this study experimentally tested six specimens for investigating the effects of using varied recycled aggregate content (0%, 50%, and 100%) in infill concrete material of stainless steel tube beams strengthened with CFRP sheets. Additionally, several finite element RCFSST models were built and analyzed to numerically investigate the effects of further parameters, such as the varied width-to-thickness ratios and yield strengths. Generally, the results showed that using 100% recycled aggregates in infill concrete material reduced the RCFSST beam’s bending capacity by about 15% when compared to the corresponding control specimen (0% recycled aggregate), with little difference in the failure mode behavior. Pre-damaged RCFSST beam capacity showed significant improvement (43.6%) when strengthened with three CFRP layers. The RCFST model with a lower w/t ratio showed better-strengthening performance than those with a higher ratio, where, the models with w/t ratios equal to 15 and 48 achieved a bending capacity improvement equal to about 18% and 35%, respectively, as an example. Furthermore, the results obtained from the current study are well compared by those predicted using the existing analytical methods.