Volatile fatty acids (VFA) can be used as the additional carbon source of biological nutrient removal (BNR), and the increase of propionic acid percentage in VFA has been reported to facilitate the performance of BNR. In this study a new method for significantly improving the propionic acid fraction in VFA derived from waste activated sludge was reported, which included (1) mixing food waste with sludge and pre-fermenting the mixture (first stage), and (2) separating the mixture, sterilizing the pre-fermentation liquid and fermenting it after inoculating Propionibacterium acidipropionici (second stage). By optimizing the first stage with response surface methodology, a propionic acid content of 68.4% with propionic acid concentration of 7.13 g COD/L could be reached in the second stage, which was much higher than that reported previously. Lactic acid was found to be the most abundant product of the first stage and it served as the substrate for propionic acid production in the second stage. Further investigation showed that during the first stage the addition of food waste to the pre-fermentation system of sludge significantly increased the generation of lactic acid due to the synergistic effect, which resulted in the improvement of propionic acid production in the second stage. Finally, the use of propionic acid-enriched VFA as a superior carbon source of BNR was tested, and its performance was observed to be much better than using acetic acid-enriched VFA derived from sludge by the previously documented method.