Examples of the present disclosure provide a message relay service. The message relay service provides an application programming interface (API) with which messages can be sent and received without handling specific implementation details of a messaging system. When inbound messages are received, the message relay service may provide a push notification and/or may store the message for later access. In examples, one or more source addresses are used to send messages. If the client device indicates a group of addresses should be used, one address is selected from the group and used to send a message accordingly. In some examples, the message relay service determines that a messaging gateway need not be used to message a recipient address, and transmits the message without use of the messaging gateway. The same API may be used to send and receive messages across different messaging systems without a customer handling system-specific complexities.