Anaerobic co-digestion of various organic wastes has been shown to improve biogas yield of fish wastes. This paper presents the effect of pre-treating Nile perch fish solid waste (FSW) using CBR-11 bacterial culture (CBR-11-FSW) and commercial lipase enzyme (Lipo-FSW), followed by batch anaerobic co-digestion with vegetable fractions of market solid waste (VFMSW) in various proportions, using potato waste (PW) and cabbage waste (CW) as co-substrates either singly or combined. Results indicated that CBR-11 pre-treated FSW co-digested with PW or CW in 1:1 ratio (substrate: inoculum) had positive effect on methane yield, while Lipo pre-treated FSW had negative effect on methane yield. Using CBR-11-FSW:PW the highest yield was 1.58 times more than the untreated FSW. Whereas, using Lipo-FSW:CW the highest yield was 1.65 times lower than un-treated FSW. Furthermore, the optimal mixture of CBR-11 pre-treated FSW and PW and CW co-substrates resulted into higher methane yield of 1, 322 CH4 ml/gVS using CBR-11-FSW (10):PW (45):CW (45) ratio. The ratio enhanced methane yield to 135% compared to control. In conclusion, results demonstrates that optimal mixture of CBR-11 pre-treated FSW with both PW and CW as co-substrates enhanced methane yield and provide base line data for potential application in continuous anaerobic bioreactors investigation.