Subject matter includes systems and methods for presence-based messaging. In one implementation an engine detects the real-time presence of a potential message recipient who can be reached via a communications medium that a sender composing a message is not currently using. The engine can either transition to an environment for composing and sending the message using the detected presence-based communications medium or offer the sender a choice of switching to the presence-based communication medium.