In order to identify whether formal measures of complexity can predict the human judgement of rhythm complexity, we artificially generated 48 rhythmic sequences, and measured their complexity according to five measures from information theory and algorithmic complexity (Shannon entropy, entropy rate, excess entropy, transient information, and Kolmogorov complexity). We designed a rhythm perception experiment, in which 32 participants guessed the last beat of each sequence and indicated the difficulty of doing so, aided by a visual representation of the length of each sequence. The participants completed a short version of the Raven’s Matrices and the Gold-MSI questionnaire in order to quantify their general pattern identification ability and several aspects of their musical expertise. The average prediction accuracy for each sequence was correlated with their entropy rate and Kolmogorov complexity, and the average judgement of the task difficulty for each sequence was highly correlated with their entropy rate and Kolmogorov complexity. The participants’ overall score on the rhythm perception task was correlated with their self-assessed musical perceptual abilities. Finally, a logistic regression showed main effects of entropy rate, Kolmogorov complexity, and musical training, and interactions between these two measures of complexity and musical training. Our results show that formal measures of complexity capture some aspects of human rhythm perception, and more specifically that the perception of rhythm complexity scales with departure from periodicity. Moreover, we add to the body of evidence showing the effect of musical expertise on music perception. Tentative interpretations are provided, as well as suggestions for further research.