The present work reports on the characterization of cellulose nanowhiskers (CNW) extracted from three different food by-products, i.e., wheat straw (WSCNW), Brewers spent grains (BGCNW) and olive pomace (OPCNW), by using an optimized hydrolysis method similar to that developed to extract bacterial cellulose nanowhiskers (BCNW). WSCNW and BGCNW were seen to present optimal properties, with aspect ratio, crystallinity and thermal stability values comparable to those of BCNW. Additionally, the optimized hydrolysis treatment led to extraction yields higher than those previously reported for food by-products. The CNW were subsequently incorporated into a commercial polyhydroxybutyrate-co-valerate polymer (PHBV) by solution casting, and the produced nanocomposites were characterized. Although the addition of BGCNW and WSCNW was advantageous in terms of mechanical performance in comparison with OPCNW, no significant enhancement of the pure PHBV mechanical properties was reported because of the low nanofiller loadings used and the inherent difficulty of achieving a high degree of dispersion by the casting method. Interestingly, BGCNW and WSCNW presented reduced moisture sensitivity as compared with BCNW, leading to greater barrier performance and resulting in oxygen permeability reductions up to 26 % with WSCNW and 44 % with BGCNW.