A protocol for automatically fixing broken hypertext links is described that can save countless hours wasted by World-Wide Web surfers trying to navigate using a broken link or web authors trying to fix broken links to their web pages. A link correction service checks hypertext links in a document by sending messages according to a hyperlink verification protocol (HLVP) to a remote web server indicated by the link. A link checking service at the remote web server, in response to receiving an HLVP message for a link, consults a mapping table to determine if the link is valid, has changed, has been removed, or is unknown. A response code indicating the status of the link is returned to the link correction service to modify the page accordingly.