The complexes produced by mixing oppositely charged starches containing aldehyde groups (cationic aldehyde starch, CAS, and anionic aldehyde starch, AAS) were compared with complexes consisting of polyamidoamine epichlorohydrine (PAE) and AAS regarding adsorption properties and efficiency in providing paper strength. Quartz crystal microbalance with dissipation (QCM-D) studies showed that the complex of CAS and AAS adsorbed less on the model film of nanofibrillated cellulose (NFC) than CAS by itself due to the acetal and hydrogen bonds formation in the complex structure blocking available groups to be adsorbed. The wet tensile index of the paper produced with CAS-AAS complex also decreased, and this was attributed to less adsorption on the cellulose surface, as indicated by the QCM-D results. At a higher concentration, the aldehyde starch complexes provided better tensile strength than the CAS addition. The adsorbed amount of PAE-AAS complex onto cellulose model film was more than PAE. This complexation decreased PAE efficiency in giving the wet tensile strength while dry strength of the paper increased at further complex addition. Atomic force microscopy (AFM) results showed that CAS-AAS complexes filled gaps between fibrils making a more flattened layer due to the higher adsorption and bigger particle size compared to the PAE-AAS complex.