Coronal holes are thought to be composed of relatively broad columnar structures known as plumes. Here, we demonstrate that the plumes (and interplumes) in polar coronal holes are composed of fine-scale filamentary structure, with average scales of 2″–10″. The fine structure is the off-limb analog of the previously found “plumelets” of Uritsky et al. The off-limb observations enable an examination of the fine structure without the influence of the underlying atmosphere along the line of sight. Hence, we show that the fine-scale structure is present at least until the edge of the field of view of the Solar Dynamics Observatory. The fine structure is found to have spatial distribution that follows a k −1 power law perpendicular to the inferred magnetic field direction. For a small sample of the fine structure, the cross-sectional profiles are measured as a function of height. In some cases, the measurements indicate that the fine structure expands super-radially, consistent with existing models of polar field expansion and the expansion of the plumes. We discuss the implications of the presence of the fine structure with respect to understanding wave propagation in the coronal holes and their contribution to powering the solar wind.