We explored the extent to which working memory underpins the processing of relational information in melodies. Using a between subjects design, one group of participants was primed with a melodic stream while performing a concurrent 2-back task while the other group was also primed with the melodic stream but did not perform a concurrent task. Participants were then given a melodic relational categorization task where relations (melodic contour) could either match or not match the primed melody. Reaction times on the categorization task for primed melodies were faster than for non-primed melodies, but only in the no-task condition, suggesting that relational information in melodies influenced behavior only under conditions where working memory resources were not being used. These results suggest that working memory may be a prerequisite for the processing of relational melodic content.