A novel strategy for coating extensible fibers is revealed from the study of the 'silk' tethers produced by marine mussels. The tethers, known as byssal threads, are molded collagenous fibers coated with a thin (2-4 microm) cuticle that protects the fibrillar core from abrasion and bacterial attack. One mussel species infuses the cuticle with nanoscale granules, which increase the extensibility of the hard coating by to 70%, making it seven times stretchier than any synthetic polymer coating. The mussel cuticle could therefore inspire new strategies for the design and manufacture of thin composite coatings that are both hard and extensible.