A facility for processing a search query is described. The facility identifies one or more items that satisfy the query, at least one of which is a media sequence. For each identified media sequence, the facility identifies an advertising message based upon the contents of the query. In response to the query, the facility returns a search result that indicates the identified items. When one of the identified media sequences is selected in the search result, the selected media sequence is provided in conjunction with the advertising message identified for it.