Complex signaling behaviors, such as avian song and courtship displays, have been associated with increases in both absolute and relative brain size, presumably mediated by relationships between brain size and motor coordination and learning abilities. Nonetheless, reliably establishing these relationships is challenging due to the difficulty of quantifying behavioral complexity. Birds-of-paradise perform some of the most elaborate avian courtship displays, involving a striking degree of complexity and motor coordination, which makes them interesting models for investigating the evolution of complex motor learning abilities in birds. Here, we compiled a µCT-based brain size dataset of more than half of the known species of birds-of-paradise and used multiple metrics of display complexity to test the hypothesis that larger brains are associated with more elaborate repertoires of motor and vocal displays. We found no clear evidence that the complexity of courtship display behaviors coevolved with brain size among the birds-of-paradise: this conclusion held across 3 kinds of behavioral and 2 kinds of vocal complexity scores.