Nanocellulose membranes based on tunicate-derived cellulose nanofibers, starch, and ~5% wood-derived lignin were investigated using three different types of lignin. The addition of lignin into cellulose membranes increased the specific surface area (from 5 to ~50 m²/g), however the fine porous geometry of the nanocellulose with characteristic pores below 10 nm in diameter remained similar for all membranes. The permeation of H₂, CO₂, N₂, and O₂ through the membranes was investigated and a characteristic Knudsen diffusion through the membranes was observed at a rate proportional to the inverse of their molecular sizes. Permeability values, however, varied significantly between samples containing different lignins, ranging from several to thousands of barrers (10⁻¹⁰ cm³ (STP) cm cm⁻² s⁻¹ cmHg⁻¹cm), and were related to the observed morphology and lignin distribution inside the membranes. Additionally, the addition of ~5% lignin resulted in a significant increase in tensile strength from 3 GPa to ~6–7 GPa, but did not change thermal properties (glass transition or thermal stability). Overall, the combination of plant-derived lignin as a filler or binder in cellulose–starch composites with a sea-animal derived nanocellulose presents an interesting new approach for the fabrication of membranes from abundant bio-derived materials. Future studies should focus on the optimization of these types of membranes for the selective and fast transport of gases needed for a variety of industrial separation processes.