To add a contact to Windows Messenger, go to Tools and click on the Add a Contact link.