According to Leibniz ‘Music is the hidden arithmetical exercise of a mind unconscious that it is calculating.’ The perception or experience of time is an essential aspect of listeners’ engagement with music. As such listeners’ experience of rhythmic patterns and their aesthetic response can enhance our understanding of the perception of time. Studies by Berlyne suggest that aesthetic evaluations are low for stimuli that are too simple or too complex with a preference for intermediate level of complexity. In musical terms we would expect listeners to respond negatively to music that is purely repetitive or to music that seems incomprehensibly random and to prefer music that manages to balance familiarity with variation. We present a study that aims to match listeners’ evaluation of rhythmic complexity with computational measures of complexity. We selected five measures derived from information theory - Shannon’s entropy, entropy rate, excess entropy, transient information, and Kolmogorov complexity. Rhythmic sequences, covering a wide spectrum of complexity levels according to these measures, were generated algorithmically as binary sequences. These sequences were synthesized as drum patterns with 1s as hits and 0s as rests. 32 participants were asked to guess whether the last beat of each sequence was supposed to be a drum hit or a rest. We averaged the participants’ scores in order to assign an implicit rating of rhythm complexity to each sequence. We also obtained an explicit rating of complexity by asking the participants to rate the perceived difficulty of guessing the last beat for each sequence. Finally, the participants completed the Gold-MSI questionnaire and a shortened version of the Raven’s matrices, in order to investigate the effects of musicality and visual pattern identification on the perception of rhythm complexity. The Kolmogorov complexity of the sequences was correlated with the scores on the explicit task (r = .973, p < .001), and the entropy rate of the sequences was correlated with the scores on both implicit (r = .670, p = .012) and explicit tasks (r = .909, p < .001). There was also a Kolmogorov complexity-by-musicality interaction (F = 5.498, p = .026), confirming the influence of musical expertise in the perception of rhythm complexity. There was no effect of the scores on the Raven’s matrices, showing that auditory sequence perception and visual pattern identification seem to be different abilities. These results show that information-theoretical concepts capture some salient features of rhythm perception, and provide the framework for further studies on the aesthetic perception of rhythm.