Ubiquitin modifications of target proteins act to localise, direct and specify a diverse range of cellular processes, many of which are biomedically relevant. To allow this diversity, ubiquitin modifications exhibit remarkable complexity, determined by a combination of polyubiquitin chain length, linkage type, numbers of ubiquitin chains per target, and decoration of ubiquitin with other small modifiers. However, many questions remain about how different ubiquitin signals are specifically recognised and transduced by the decoding ubiquitin-binding domains (UBDs) within ubiquitin-binding proteins. This review briefly outlines our current knowledge surrounding the diversity of UBDs, identifies key challenges in their discovery and considers recent structural studies with implications for the increasing complexity of UBD function and identification. Given the comparatively low numbers of functionally characterised polyubiquitin-selective UBDs relative to the ever-expanding variety of polyubiquitin modifications, it is possible that many UBDs have been overlooked, in part due to limitations of current approaches used to predict their presence within the proteome. Potential experimental approaches for UBD discovery are considered; web-based informatic analyses, Next-Generation Phage Display, deubiquitinase-resistant diubiquitin, proximity-dependent biotinylation and Ubiquitin-Phototrap, including possible advantages and limitations. The concepts discussed here work towards identifying new UBDs which may represent the ‘dark matter’ of the ubiquitin system.