Polyelectrolyte complexes are routinely used as adhesives to strengthen fiber-fiber contacts in paper. This work evaluates different approaches to putting the polyelectrolyte complexes into the adhesive joint. Instead of conventional wet paper mechanical testing, a wet cellulose film delamination technique was employed permitting direct comparison of different approaches to applying the polymeric adhesive to the cellulose-cellulose joint. The adhesion strengths of layer-by-layer polyelectrolyte complexes assembled on wet cellulose films and the adhesion strengths of the corresponding polyelectrolyte complex coated on wet cellulose films are compared. The wet adhesion strengths were measured by peel delamination. The polyelectrolyte complexes were based on mixtures of cationic polyvinylamine (PVAm) and anionic carboxymethyl cellulose (CMC). The layer-by-layer assemblies of PVAm and CMC yielded stronger wet adhesion than did coated films of the corresponding colloidal complexes or pure PVAm at the same coverage (mass of polymer/joint area). The role of CMC was to give ionic crosslinks with PVAm which increase the cohesive strength of thick PVAm layers. PVAm gives much stronger wet adhesion to cellulose compared to the oxidized silicon wafer surfaces. It is proposed that imine and aminal bonds can form between the polyamine and hemiacetals in the regenerated cellulose films which cannot form with silica.