Methods and systems for performing speech recognition using an electronic interactive agent are disclosed. In embodiments of the invention, an electronic agent is presented in a form perceptible to a user. The electronic agent is used to solicit speech input from a user and to respond to the user's recognized speech, and mimics the behavior of a human agent in a natural language query session with the user. The electronic agent may be implemented in a distributed speech recognition system in which speech recognition tasks are divided between client and server.