Programming automated Web Navigation Assistants, i.e., applications that automatically navigate the Web performing specific tasks for the user, is far from easy. Since HTML pages offered by legacy Web-based applications are designed to be manipulated only by people using browsers, and Web pages contain semi-structured information [3] whose data schema may be easily changed, the creation and, even worse, the maintenance of this kind of applications, is very expensive. However, an increasing amount of information sources and online applications have been added to the Web during the last few years, so assistants for automating tasks over those Web-enabled applications, are more and more needed. These assistants may automate tasks by filling in forms, following links, analyzing data embedded in Web pages and performing computations over those data on behalf of the user. Software engineering techniques are clearly needed to reduce the cost of, not just creating these programs (by significatively reducing their time-to-market), but even more importantly, maintaining them working properly, reducing the cost of readapting them to Web site pages whose structure or navigation schemes are frequently changed. This paper proposes the well known formal method Message Sequence Charts (MSC) [12] as a base for defining a language for programming Web Navigation Assistants which may navigate a Web site according to the user?s aims. This specification language, called XPlore, is specially suited for both requirements engineering and automatic generation of an executable, and has been successfully tested on several well known Web sites.