Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for a search dialog user interface. In one aspect, a method includes displaying a search using interface, comprising: a search dialog user interface in which a plurality of search threads are initiated, each search thread comprising a plurality of entries, wherein the entries comprise: one or more query messages, each query message being descriptive of one or more search criteria, one or more result messages, each result message being a message describing criteria for a corresponding search and that is responsive to one or more preceding query messages within the search thread; and a search result display location in which search results corresponding to an active result message are displayed.