Disclosed are various embodiments for using relevance indications provided by a user in performing a search. Search results corresponding to a search query are provided to a user of a client computing device. The user provides a relevance indication corresponding to relevance of at least one of the search results. A subsequent search is performed which takes the relevance indication into account.