Sugarcane bagasse (SCB) is the main residue obtained from sugarcane processing, and it has been widely investigated as a strategic renewable energy source. The typical recalcitrant characteristic of SCB requires the use of pretreatments (e.g., chemicals) to increase methane production through anaerobic digestion, which is normally reported to generate toxic effluents and increase operational costs. Based on this, the present study evaluated the efficiency of an inexpensive, alternative, and more sustainable method to improve the biodegradability of SCB and increase methane production by pre-storing it with acidic organic biowastes, such as cheese whey (CW) and fruit and vegetable waste (FVW). Different fresh weight-based proportions of FVW (5:95, 10:90, and 15:85) and CW (10:90, 20:80, and 25:75) were soaked with SBC for 7 days at 25 °C. These treatments were compared with traditional alkaline pretreatment using NaOH at concentrations of 1%, 5%, and 10% (w/v). The best result was obtained with SCB + FVW (5:95), being 520 ± 7 NL CH4 kg VS−1 (27.6% higher than the control) with degradation time (T90) reduced from 13 to 7 days. Pretreatment with SBC + CW resulted in antagonistic effects due to process inhibition, while alkaline pretreatment with NaOH at concentrations of 5% and 10% similarly increased methane yield by 21.2% and 34.1%, respectively. Therefore, pre-storage of SBC with FVW proved to be the best strategy to increase methane production from SCB, while simultaneously avoiding the use of chemical reagents that result in toxic effluents.