The study investigated the correlation between the intensity of the Aha! experience and participants' subjective difficulty ratings of problems before and after finding their solutions. We assumed that the Aha! experience arises from a shift in processing fluency triggered by changing from an initially incoherent problem representation to a coherent one, which ultimately leads to the retrieval of a solution with unexpected ease and speed. First, we hypothesized that higher Aha! experience ratings would indicate more sudden solutions, manifesting in a reduced correlation between the initial difficulty ratings and solution times. Second, we hypothesized that higher Aha! experience ratings would correspond to a greater shift in the subjective difficulty ratings between the initial and retrospective assessments. To test our hypotheses, we developed a novel set of rebus puzzles. A total of 160 participants solved rebuses and provided initial (within 5 s of problem presentation) and retrospective difficulty ratings (following the generation or presentation of a correct solution). They also rated their Aha! experience (after solution generation or presentation), confidence in solutions, and the likability of each rebus. Our findings revealed that the initial ratings of the problem's subjective difficulty were positively correlated with the solution time and that this correlation decreased in the case of a stronger Aha! experience. Aha! experience ratings were positively correlated with the differences between initial and retrospective difficulty ratings, confidence, solution accuracy, and rebus likability. We interpreted our results to be in line with the processing fluency and metacognitive prediction error accounts.