Techniques are described for employing a queue service as an intermediary to communicate messages between separate networks. A first proxy service may access a request generated by a client device operating in a first network, the request initially indicating a destination that is a server device operating in a second network. The request may be an application level protocol request. The first proxy service may modify the request to include, as a destination, a queue maintained by a queue service that is accessible from the first and second networks. The first proxy service may enqueue the modified request in the queue. A second proxy service operating in the second network may retrieve the enqueued request and communicate the request to the server device. One or more responses generated by the server device may be enqueued in a queue by the second proxy service for delivery to the client device.