A query modality recommendation system provides recommendations to use a particular query modality based on one or more categories of search results for a search query. Upon receiving a search query in a first query modality at a search engine, the query modality recommendation system determines to recommend use of a second query modality based on one or more categories of the search results. For example, the first query modality may be a textual query and the second query modality may be an image query. In aspects, recommending use of the second query modality comprises comparing a first search performance of the one or more categories for the first query modality in historical search queries to a second search performance of the one or more categories for the second query modality in the historical search queries.