Nematic liquid crystal elastomers (LCEs) have anomalously high vibration damping, and it has been assumed this is the cause of their anomalously high pressure-sensitive adhesion (PSA). Here we investigate the mechanism behind this enhanced PSA by first preparing thin adhesive tapes with LCE of varying crosslinking density, characterizing their material and surface properties, and then studying the adhesion characteristics with a standard set of 90-deg peel, lap shear, and probe tack tests. The study confirms that the enhanced PSA is only present in (and due to) the nematic phase of the elastomer, and the strength of bonding takes over 24 hours to fully reach its maximum value. Such a long saturation time is caused by the slow relaxation of local stress and director orientation in nematic domains after pressing against the surface. We confirm this mechanism by showing that a freshly pressed and annealed tape reaches the same maximum bonding strength on cooling, when the returning nematic order is forming in its optimal configuration in the pressed film.