The permeability of the polymer walls of polyalkylcyanoacrylate nanocapsules varies by different degrees of chemical cross-linking. For this reason, different amounts of bivalent alkylcyanoacrylates are added to the monovalent alkylcyanoacrylate prior to an interfacial polymerization step in order to generate capsules with various cross-linking densities. The obtained nanocapsules are characterized by observing the water molecules via pulsed field-gradient nuclear magnetic resonance using a stimulated echo sequence. The resulting echo decay plots reveal the exchange rate of the water molecules between the free and encapsulated states. The observed dwell times of water molecules in the encapsulated state are characteristic parameters for the permeability of the given capsule membranes. They show a clear dependence on the degree of cross-linking, proving the potential of this approach for a controlled variation of the capsule permeability. Also, the cross-linked nanocapsules exhibit a significantly decreased solubility in tetrahydrofuran which may lead to new applications for polyalkylcyanoacrylate nanocapsules in organic solvents.