Food packaging is essential to avoid food waste, which is a major contributor to global emissions. The vast majority of food packaging materials are made from petroleum-derived plastic, contributing substantially to the plastic waste crisis. Cellulosic paper is a biobased and biodegradable alternative packaging material, but its use is limited by its extremely poor barrier to oxygen, water, water vapor, and grease, all of which contribute to early degradation of food products. Typical coatings for paper are unsustainable and inhibit its biodegradability. In this work, a water-based, fully bioderived polyelectrolyte complex coating consisting of chitosan, pectin, and carnauba wax is applied to kraft paper to improve its resistance to oxygen, water, and grease. After a thermal annealing step, the coatings exhibit continuous phases of wax and polyelectrolytes, resulting in a combination of both oxygen and water resistance. The best-performing coating substantially improves oxygen transmission rate (from 12.5 million to 155,000 cm3 m-2 day-1), water vapor barrier (from 346 to 304 g m-2 day-1), water absorptivity (from 131.6 to 29.1 g m-2) and castor oil absorptivity (from 94 to 53 g m-2), with minimal coat weight. This work advances the development of fully sustainable food packaging to address the major environmental crises of plastic and food waste.