Systems and methods are described for establishing a connection between a client and a server that are each communicating via a network. The methods and techniques may be used, for example, to establish a media streaming connection between a media player and a placeshifting device when a firewall or other impediment to direct network connections exists. A relay server receives connection requests from the client and from the server via the network. In response to receiving the requests, a first connection is established between the relay server and the client and a second connection between the relay server and the server. Data received by the relay server on each of the first and second connections is relayed to the other of the first and second connections to thereby establish the connection between the client and the server via the relay server.