In general, the subject matter described in this specification can be embodied in methods, systems, and program products for performing searches with gesture-based input. A search system receives gesture data corresponding to one or more characters that have been drawn on a display of a client device. The search system recognizes the one or more characters that correspond to the gesture data. The search system formulates a search that includes the one or more characters as a query term. The search system communicates to the client device one or more search results for the search, and data identifying the one or more characters.