Super-strong carbon nanotube (CNT) fibers are fabricated by infiltration of the mussel-inspired underwater adhesives, poly(ethylenimine)-catechols (PEI-Cs). PEI-C mimics the amino acid sequence of mussel adhesive proteins in which catechols from 3,4-dihydroxyl-L-phenylalanine and amines from lysine are found. Weak interactions between CNTs are overcome by heat-induced, metal-catalyzed chemical crosslinking of catechol. PEI-C's strong and versatile adhesion results in high-strength CNT fibers.