diff --git a/src/lang/english.txt b/src/lang/english.txt
--- a/src/lang/english.txt
+++ b/src/lang/english.txt
@@ -2166,6 +2166,7 @@ STR_NETWORK_CLIENT_LIST_CLIENT_COMPANY_C
 STR_NETWORK_CLIENT_LIST_SERVER_CONNECTION_TYPE_UNKNOWN          :{BLACK}Local
 STR_NETWORK_CLIENT_LIST_SERVER_CONNECTION_TYPE_ISOLATED         :{RED}Remote players can't connect
 STR_NETWORK_CLIENT_LIST_SERVER_CONNECTION_TYPE_DIRECT           :{BLACK}Public
+STR_NETWORK_CLIENT_LIST_SERVER_CONNECTION_TYPE_STUN             :{BLACK}Behind NAT
 ############ End of ConnectionType
 
 STR_NETWORK_CLIENT_LIST_ADMIN_CLIENT_KICK                       :Kick
diff --git a/src/network/CMakeLists.txt b/src/network/CMakeLists.txt
--- a/src/network/CMakeLists.txt
+++ b/src/network/CMakeLists.txt
@@ -24,6 +24,8 @@ add_files(
     network_internal.h
     network_server.cpp
     network_server.h
+    network_stun.cpp
+    network_stun.h
     network_type.h
     network_udp.cpp
     network_udp.h
diff --git a/src/network/core/CMakeLists.txt b/src/network/core/CMakeLists.txt
--- a/src/network/core/CMakeLists.txt
+++ b/src/network/core/CMakeLists.txt
@@ -28,6 +28,8 @@ add_files(
     tcp_http.cpp
     tcp_http.h
     tcp_listen.h
+    tcp_stun.cpp
+    tcp_stun.h
     udp.cpp
     udp.h
 )
diff --git a/src/network/core/address.cpp b/src/network/core/address.cpp
--- a/src/network/core/address.cpp
+++ b/src/network/core/address.cpp
@@ -313,13 +313,12 @@ static SOCKET ListenLoopProc(addrinfo *r
 		Debug(net, 1, "Setting no-delay mode failed: {}", NetworkError::GetLast().AsString());
 	}
 
-	int on = 1;
-	/* The (const char*) cast is needed for windows!! */
-	if (setsockopt(sock, SOL_SOCKET, SO_REUSEADDR, (const char*)&on, sizeof(on)) == -1) {
+	if (!SetReusePort(sock)) {
 		Debug(net, 0, "Setting reuse-address mode failed: {}", NetworkError::GetLast().AsString());
 	}
 
 #ifndef __OS2__
+	int on = 1;
 	if (runp->ai_family == AF_INET6 &&
 			setsockopt(sock, IPPROTO_IPV6, IPV6_V6ONLY, (const char*)&on, sizeof(on)) == -1) {
 		Debug(net, 3, "Could not disable IPv4 over IPv6: {}", NetworkError::GetLast().AsString());
@@ -401,16 +400,45 @@ void NetworkAddress::Listen(int socktype
 }
 
 /**
+ * Get the peer address of a socket as NetworkAddress.
+ * @param sock The socket to get the peer address of.
+ * @return The NetworkAddress of the peer address.
+ */
+/* static */ NetworkAddress NetworkAddress::GetPeerAddress(SOCKET sock)
+{
+	sockaddr_storage addr = {};
+	socklen_t addr_len = sizeof(addr);
+	if (getpeername(sock, (sockaddr *)&addr, &addr_len) != 0) {
+		Debug(net, 0, "Failed to get address of the peer: {}", NetworkError::GetLast().AsString());
+		return NetworkAddress();
+	}
+	return NetworkAddress(addr, addr_len);
+}
+
+/**
+ * Get the local address of a socket as NetworkAddress.
+ * @param sock The socket to get the local address of.
+ * @return The NetworkAddress of the local address.
+ */
+/* static */ NetworkAddress NetworkAddress::GetSockAddress(SOCKET sock)
+{
+	sockaddr_storage addr = {};
+	socklen_t addr_len = sizeof(addr);
+	if (getsockname(sock, (sockaddr *)&addr, &addr_len) != 0) {
+		Debug(net, 0, "Failed to get address of the socket: {}", NetworkError::GetLast().AsString());
+		return NetworkAddress();
+	}
+	return NetworkAddress(addr, addr_len);
+}
+
+/**
  * Get the peer name of a socket in string format.
  * @param sock The socket to get the peer name of.
  * @return The string representation of the peer name.
  */
 /* static */ const std::string NetworkAddress::GetPeerName(SOCKET sock)
 {
-	sockaddr_storage addr;
-	socklen_t addr_len = sizeof(addr);
-	getpeername(sock, (sockaddr *)&addr, &addr_len);
-	return NetworkAddress(addr, addr_len).GetAddressAsString();
+	return NetworkAddress::GetPeerAddress(sock).GetAddressAsString();
 }
 
 /**
diff --git a/src/network/core/address.h b/src/network/core/address.h
--- a/src/network/core/address.h
+++ b/src/network/core/address.h
@@ -175,6 +175,8 @@ public:
 
 	static const char *SocketTypeAsString(int socktype);
 	static const char *AddressFamilyAsString(int family);
+	static NetworkAddress GetPeerAddress(SOCKET sock);
+	static NetworkAddress GetSockAddress(SOCKET sock);
 	static const std::string GetPeerName(SOCKET sock);
 };
 
diff --git a/src/network/core/config.cpp b/src/network/core/config.cpp
--- a/src/network/core/config.cpp
+++ b/src/network/core/config.cpp
@@ -39,9 +39,19 @@ const char *NetworkCoordinatorConnection
 }
 
 /**
+ * Get the connection string for the STUN server from the environment variable OTTD_STUN_CS,
+ * or when it has not been set a hard coded default DNS hostname of the production server.
+ * @return The STUN server's connection string.
+ */
+const char *NetworkStunConnectionString()
+{
+	return GetEnv("OTTD_STUN_CS", "stun.openttd.org");
+}
+
+/**
  * Get the connection string for the content server from the environment variable OTTD_CONTENT_SERVER_CS,
  * or when it has not been set a hard coded default DNS hostname of the production server.
- * @return The game coordinator's connection string.
+ * @return The content server's connection string.
  */
 const char *NetworkContentServerConnectionString()
 {
@@ -51,7 +61,7 @@ const char *NetworkContentServerConnecti
 /**
  * Get the connection string for the content mirror from the environment variable OTTD_CONTENT_MIRROR_CS,
  * or when it has not been set a hard coded default DNS hostname of the production server.
- * @return The game coordinator's connection string.
+ * @return The content mirror's connection string.
  */
 const char *NetworkContentMirrorConnectionString()
 {
diff --git a/src/network/core/config.h b/src/network/core/config.h
--- a/src/network/core/config.h
+++ b/src/network/core/config.h
@@ -13,6 +13,7 @@
 #define NETWORK_CORE_CONFIG_H
 
 const char *NetworkCoordinatorConnectionString();
+const char *NetworkStunConnectionString();
 const char *NetworkContentServerConnectionString();
 const char *NetworkContentMirrorConnectionString();
 
@@ -20,6 +21,7 @@ const char *NetworkContentMirrorConnecti
 static const char * const NETWORK_CONTENT_MIRROR_URL            = "/bananas";
 
 static const uint16 NETWORK_COORDINATOR_SERVER_PORT = 3976;           ///< The default port of the Game Coordinator server (TCP)
+static const uint16 NETWORK_STUN_SERVER_PORT        = 3975;           ///< The default port of the STUN server (TCP)
 static const uint16 NETWORK_CONTENT_SERVER_PORT     = 3978;           ///< The default port of the content server (TCP)
 static const uint16 NETWORK_CONTENT_MIRROR_PORT     =   80;           ///< The default port of the content mirror (TCP)
 static const uint16 NETWORK_DEFAULT_PORT            = 3979;           ///< The default port of the game server (TCP & UDP)
@@ -47,7 +49,7 @@ static const uint16 COMPAT_MTU          
 static const byte NETWORK_GAME_ADMIN_VERSION        =    1;           ///< What version of the admin network do we use?
 static const byte NETWORK_GAME_INFO_VERSION         =    5;           ///< What version of game-info do we use?
 static const byte NETWORK_COMPANY_INFO_VERSION      =    6;           ///< What version of company info is this?
-static const byte NETWORK_COORDINATOR_VERSION       =    2;           ///< What version of game-coordinator-protocol do we use?
+static const byte NETWORK_COORDINATOR_VERSION       =    3;           ///< What version of game-coordinator-protocol do we use?
 
 static const uint NETWORK_NAME_LENGTH               =   80;           ///< The maximum length of the server name and map name, in bytes including '\0'
 static const uint NETWORK_COMPANY_NAME_LENGTH       =  128;           ///< The maximum length of the company name, in bytes including '\0'
diff --git a/src/network/core/os_abstraction.cpp b/src/network/core/os_abstraction.cpp
--- a/src/network/core/os_abstraction.cpp
+++ b/src/network/core/os_abstraction.cpp
@@ -160,6 +160,23 @@ bool SetNoDelay(SOCKET d)
 }
 
 /**
+ * Try to set the socket to reuse ports.
+ * @param d The socket to reuse ports on.
+ * @return True if disabling the delaying succeeded, otherwise false.
+ */
+bool SetReusePort(SOCKET d)
+{
+#ifdef _WIN32
+	/* Windows has no SO_REUSEPORT, but for our usecases SO_REUSEADDR does the same job. */
+	int reuse_port = 1;
+	return setsockopt(d, SOL_SOCKET, SO_REUSEADDR, (const char *)&reuse_port, sizeof(reuse_port)) == 0;
+#else
+	int reuse_port = 1;
+	return setsockopt(d, SOL_SOCKET, SO_REUSEPORT, &reuse_port, sizeof(reuse_port)) == 0;
+#endif
+}
+
+/**
  * Get the error from a socket, if any.
  * @param d The socket to get the error from.
  * @return The errno on the socket.
diff --git a/src/network/core/os_abstraction.h b/src/network/core/os_abstraction.h
--- a/src/network/core/os_abstraction.h
+++ b/src/network/core/os_abstraction.h
@@ -196,6 +196,7 @@ static inline socklen_t FixAddrLenForEms
 
 bool SetNonBlocking(SOCKET d);
 bool SetNoDelay(SOCKET d);
+bool SetReusePort(SOCKET d);
 NetworkError GetSocketError(SOCKET d);
 
 /* Make sure these structures have the size we expect them to be */
diff --git a/src/network/core/tcp.h b/src/network/core/tcp.h
--- a/src/network/core/tcp.h
+++ b/src/network/core/tcp.h
@@ -99,6 +99,7 @@ private:
 
 	std::string connection_string;                      ///< Current address we are connecting to (before resolving).
 	NetworkAddress bind_address;                        ///< Address we're binding to, if any.
+	int family = AF_UNSPEC;                             ///< Family we are using to connect with.
 
 	void Resolve();
 	void OnResolved(addrinfo *ai);
@@ -114,7 +115,7 @@ private:
 
 public:
 	TCPConnecter() {};
-	TCPConnecter(const std::string &connection_string, uint16 default_port, NetworkAddress bind_address = {});
+	TCPConnecter(const std::string &connection_string, uint16 default_port, NetworkAddress bind_address = {}, int family = AF_UNSPEC);
 	virtual ~TCPConnecter();
 
 	/**
diff --git a/src/network/core/tcp_connect.cpp b/src/network/core/tcp_connect.cpp
--- a/src/network/core/tcp_connect.cpp
+++ b/src/network/core/tcp_connect.cpp
@@ -29,8 +29,9 @@ static std::vector<TCPConnecter *> _tcp_
  * @param default_port If not indicated in connection_string, what port to use.
  * @param bind_address The local bind address to use. Defaults to letting the OS find one.
  */
-TCPConnecter::TCPConnecter(const std::string &connection_string, uint16 default_port, NetworkAddress bind_address) :
-	bind_address(bind_address)
+TCPConnecter::TCPConnecter(const std::string &connection_string, uint16 default_port, NetworkAddress bind_address, int family) :
+	bind_address(bind_address),
+	family(family)
 {
 	this->connection_string = NormalizeConnectionString(connection_string, default_port);
 
@@ -99,6 +100,10 @@ void TCPConnecter::Connect(addrinfo *add
 		return;
 	}
 
+	if (!SetReusePort(sock)) {
+		Debug(net, 0, "Setting reuse-port mode failed: {}", NetworkError::GetLast().AsString());
+	}
+
 	if (this->bind_address.GetPort() > 0) {
 		if (bind(sock, (const sockaddr *)this->bind_address.GetAddress(), this->bind_address.GetAddressLength()) != 0) {
 			Debug(net, 1, "Could not bind socket on {}: {}", this->bind_address.GetAddressAsString(), NetworkError::GetLast().AsString());
@@ -170,6 +175,9 @@ void TCPConnecter::OnResolved(addrinfo *
 
 	/* Convert the addrinfo into NetworkAddresses. */
 	for (addrinfo *runp = ai; runp != nullptr; runp = runp->ai_next) {
+		/* Skip entries if the family is set and it is not matching. */
+		if (this->family != AF_UNSPEC && this->family != runp->ai_family) continue;
+
 		if (resort) {
 			if (runp->ai_family == AF_INET6) {
 				addresses_ipv6.emplace_back(runp);
diff --git a/src/network/core/tcp_coordinator.cpp b/src/network/core/tcp_coordinator.cpp
--- a/src/network/core/tcp_coordinator.cpp
+++ b/src/network/core/tcp_coordinator.cpp
@@ -39,6 +39,9 @@ bool NetworkCoordinatorSocketHandler::Ha
 		case PACKET_COORDINATOR_GC_CONNECT_FAILED:     return this->Receive_GC_CONNECT_FAILED(p);
 		case PACKET_COORDINATOR_CLIENT_CONNECTED:      return this->Receive_CLIENT_CONNECTED(p);
 		case PACKET_COORDINATOR_GC_DIRECT_CONNECT:     return this->Receive_GC_DIRECT_CONNECT(p);
+		case PACKET_COORDINATOR_GC_STUN_REQUEST:       return this->Receive_GC_STUN_REQUEST(p);
+		case PACKET_COORDINATOR_SERCLI_STUN_RESULT:    return this->Receive_SERCLI_STUN_RESULT(p);
+		case PACKET_COORDINATOR_GC_STUN_CONNECT:       return this->Receive_GC_STUN_CONNECT(p);
 
 		default:
 			Debug(net, 0, "[tcp/coordinator] Received invalid packet type {}", type);
@@ -94,3 +97,6 @@ bool NetworkCoordinatorSocketHandler::Re
 bool NetworkCoordinatorSocketHandler::Receive_GC_CONNECT_FAILED(Packet *p) { return this->ReceiveInvalidPacket(PACKET_COORDINATOR_GC_CONNECT_FAILED); }
 bool NetworkCoordinatorSocketHandler::Receive_CLIENT_CONNECTED(Packet *p) { return this->ReceiveInvalidPacket(PACKET_COORDINATOR_CLIENT_CONNECTED); }
 bool NetworkCoordinatorSocketHandler::Receive_GC_DIRECT_CONNECT(Packet *p) { return this->ReceiveInvalidPacket(PACKET_COORDINATOR_GC_DIRECT_CONNECT); }
+bool NetworkCoordinatorSocketHandler::Receive_GC_STUN_REQUEST(Packet *p) { return this->ReceiveInvalidPacket(PACKET_COORDINATOR_GC_STUN_REQUEST); }
+bool NetworkCoordinatorSocketHandler::Receive_SERCLI_STUN_RESULT(Packet *p) { return this->ReceiveInvalidPacket(PACKET_COORDINATOR_SERCLI_STUN_RESULT); }
+bool NetworkCoordinatorSocketHandler::Receive_GC_STUN_CONNECT(Packet *p) { return this->ReceiveInvalidPacket(PACKET_COORDINATOR_GC_STUN_CONNECT); }
diff --git a/src/network/core/tcp_coordinator.h b/src/network/core/tcp_coordinator.h
--- a/src/network/core/tcp_coordinator.h
+++ b/src/network/core/tcp_coordinator.h
@@ -38,6 +38,9 @@ enum PacketCoordinatorType {
 	PACKET_COORDINATOR_GC_CONNECT_FAILED,     ///< Game Coordinator informs client/server it has given up on the connection attempt.
 	PACKET_COORDINATOR_CLIENT_CONNECTED,      ///< Client informs the Game Coordinator the connection with the server is established.
 	PACKET_COORDINATOR_GC_DIRECT_CONNECT,     ///< Game Coordinator tells client to directly connect to the hostname:port of the server.
+	PACKET_COORDINATOR_GC_STUN_REQUEST,       ///< Game Coordinator tells client/server to initiate a STUN request.
+	PACKET_COORDINATOR_SERCLI_STUN_RESULT,    ///< Client/server informs the Game Coordinator of the result of the STUN request.
+	PACKET_COORDINATOR_GC_STUN_CONNECT,       ///< Game Coordinator tells client/server to connect() reusing the STUN local address.
 	PACKET_COORDINATOR_END,                   ///< Must ALWAYS be on the end of this list!! (period)
 };
 
@@ -48,6 +51,7 @@ enum ConnectionType {
 	CONNECTION_TYPE_UNKNOWN,  ///< The Game Coordinator hasn't informed us yet what type of connection we have.
 	CONNECTION_TYPE_ISOLATED, ///< The Game Coordinator failed to find a way to connect to your server. Nobody will be able to join.
 	CONNECTION_TYPE_DIRECT,   ///< The Game Coordinator can directly connect to your server.
+	CONNECTION_TYPE_STUN,     ///< The Game Coordinator can connect to your server via a STUN request.
 };
 
 /**
@@ -215,6 +219,50 @@ protected:
 	 */
 	virtual bool Receive_GC_DIRECT_CONNECT(Packet *p);
 
+	/**
+	 * Game Coordinator requests the client/server to do a STUN request to the
+	 * STUN server. Important is to remember the local port these STUN requests
+	 * are sent from, as this will be needed for later conenctions too.
+	 * The client/server should do multiple STUN requests for every available
+	 * interface that connects to the Internet (e.g., once for IPv4 and once
+	 * for IPv6).
+	 *
+	 *  string  Token to track the current connect request.
+	 *
+	 * @param p The packet that was just received.
+	 * @return True upon success, otherwise false.
+	 */
+	virtual bool Receive_GC_STUN_REQUEST(Packet *p);
+
+	/**
+	 * Client/server informs the Game Coordinator the result of a STUN request.
+	 *
+	 *  uint8   Game Coordinator protocol version.
+	 *  string  Token to track the current connect request.
+	 *  uint8   Interface number, as given during STUN request.
+	 *  bool    Whether the STUN connection was successful.
+	 *
+	 * @param p The packet that was just received.
+	 * @return True upon success, otherwise false.
+	 */
+	virtual bool Receive_SERCLI_STUN_RESULT(Packet *p);
+
+	/**
+	 * Game Coordinator informs the client/server of its STUN peer (the host:ip
+	 * of the other side). It should start a connect() to this peer ASAP with
+	 * the local address as used with the STUN request.
+	 *
+	 *  string  Token to track the current connect request.
+	 *  uint8   Tracking number to track current connect request.
+	 *  uint8   Interface number, as given during STUN request.
+	 *  string  Host of the peer.
+	 *  uint16  Port of the peer.
+	 *
+	 * @param p The packet that was just received.
+	 * @return True upon success, otherwise false.
+	 */
+	virtual bool Receive_GC_STUN_CONNECT(Packet *p);
+
 	bool HandlePacket(Packet *p);
 public:
 	/**
diff --git a/src/network/core/tcp_listen.h b/src/network/core/tcp_listen.h
--- a/src/network/core/tcp_listen.h
+++ b/src/network/core/tcp_listen.h
@@ -30,6 +30,42 @@ class TCPListenHandler {
 	static SocketList sockets;
 
 public:
+	static bool ValidateClient(SOCKET s, NetworkAddress &address)
+	{
+		/* Check if the client is banned. */
+		for (const auto &entry : _network_ban_list) {
+			if (address.IsInNetmask(entry)) {
+				Packet p(Tban_packet);
+				p.PrepareToSend();
+
+				Debug(net, 2, "[{}] Banned ip tried to join ({}), refused", Tsocket::GetName(), entry);
+
+				if (p.TransferOut<int>(send, s, 0) < 0) {
+					Debug(net, 0, "[{}] send failed: {}", Tsocket::GetName(), NetworkError::GetLast().AsString());
+				}
+				closesocket(s);
+				return false;
+			}
+		}
+
+		/* Can we handle a new client? */
+		if (!Tsocket::AllowConnection()) {
+			/* No more clients allowed?
+			 * Send to the client that we are full! */
+			Packet p(Tfull_packet);
+			p.PrepareToSend();
+
+			if (p.TransferOut<int>(send, s, 0) < 0) {
+				Debug(net, 0, "[{}] send failed: {}", Tsocket::GetName(), NetworkError::GetLast().AsString());
+			}
+			closesocket(s);
+
+			return false;
+		}
+
+		return true;
+	}
+
 	/**
 	 * Accepts clients from the sockets.
 	 * @param ls Socket to accept clients from.
@@ -53,41 +89,7 @@ public:
 
 			SetNoDelay(s); // XXX error handling?
 
-			/* Check if the client is banned */
-			bool banned = false;
-			for (const auto &entry : _network_ban_list) {
-				banned = address.IsInNetmask(entry);
-				if (banned) {
-					Packet p(Tban_packet);
-					p.PrepareToSend();
-
-					Debug(net, 2, "[{}] Banned ip tried to join ({}), refused", Tsocket::GetName(), entry);
-
-					if (p.TransferOut<int>(send, s, 0) < 0) {
-						Debug(net, 0, "[{}] send failed: {}", Tsocket::GetName(), NetworkError::GetLast().AsString());
-					}
-					closesocket(s);
-					break;
-				}
-			}
-			/* If this client is banned, continue with next client */
-			if (banned) continue;
-
-			/* Can we handle a new client? */
-			if (!Tsocket::AllowConnection()) {
-				/* no more clients allowed?
-				 * Send to the client that we are full! */
-				Packet p(Tfull_packet);
-				p.PrepareToSend();
-
-				if (p.TransferOut<int>(send, s, 0) < 0) {
-					Debug(net, 0, "[{}] send failed: {}", Tsocket::GetName(), NetworkError::GetLast().AsString());
-				}
-				closesocket(s);
-
-				continue;
-			}
-
+			if (!Tsocket::ValidateClient(s, address)) continue;
 			Tsocket::AcceptConnection(s, address);
 		}
 	}
diff --git a/src/network/core/tcp_stun.cpp b/src/network/core/tcp_stun.cpp
new file mode 100644
--- /dev/null
+++ b/src/network/core/tcp_stun.cpp
@@ -0,0 +1,29 @@
+/*
+ * This file is part of OpenTTD.
+ * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
+ * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/**
+ * @file tcp_stun.cpp Basic functions to receive and send STUN packets.
+ */
+
+#include "../../stdafx.h"
+#include "../../debug.h"
+#include "tcp_stun.h"
+
+#include "../../safeguards.h"
+
+/**
+ * Helper for logging receiving invalid packets.
+ * @param type The received packet type.
+ * @return Always false, as it's an error.
+ */
+bool NetworkStunSocketHandler::ReceiveInvalidPacket(PacketStunType type)
+{
+	Debug(net, 0, "[tcp/stun] Received illegal packet type {}", type);
+	return false;
+}
+
+bool NetworkStunSocketHandler::Receive_SERCLI_STUN(Packet *p) { return this->ReceiveInvalidPacket(PACKET_STUN_SERCLI_STUN); }
diff --git a/src/network/core/tcp_stun.h b/src/network/core/tcp_stun.h
new file mode 100644
--- /dev/null
+++ b/src/network/core/tcp_stun.h
@@ -0,0 +1,53 @@
+/*
+ * This file is part of OpenTTD.
+ * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
+ * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/**
+ * @file tcp_stun.h Basic functions to receive and send TCP packets to/from the STUN server.
+ */
+
+#ifndef NETWORK_CORE_TCP_STUN_H
+#define NETWORK_CORE_TCP_STUN_H
+
+#include "os_abstraction.h"
+#include "tcp.h"
+#include "packet.h"
+
+/** Enum with all types of TCP STUN packets. The order MUST not be changed. **/
+enum PacketStunType {
+	PACKET_STUN_SERCLI_STUN,  ///< Send a STUN request to the STUN server.
+	PACKET_STUN_END,          ///< Must ALWAYS be on the end of this list!! (period)
+};
+
+/** Base socket handler for all STUN TCP sockets. */
+class NetworkStunSocketHandler : public NetworkTCPSocketHandler {
+protected:
+	bool ReceiveInvalidPacket(PacketStunType type);
+
+	/**
+	 * Send a STUN request to the STUN server letting the Game Coordinator know
+	 * what our actually public IP:port is.
+	 *
+	 *  uint8   Game Coordinator protocol version.
+	 *  string  Token to track the current STUN request.
+	 *  uint8   Which interface number this is (for example, IPv4 or IPv6).
+	 *          The Game Coordinator relays this number back in later packets.
+	 *
+	 * @param p The packet that was just received.
+	 * @return True upon success, otherwise false.
+	 */
+	virtual bool Receive_SERCLI_STUN(Packet *p);
+
+public:
+	/**
+	 * Create a new cs socket handler for a given cs.
+	 * @param s  the socket we are connected with.
+	 * @param address IP etc. of the client.
+	 */
+	NetworkStunSocketHandler(SOCKET s = INVALID_SOCKET) : NetworkTCPSocketHandler(s) {}
+};
+
+#endif /* NETWORK_CORE_TCP_STUN_H */
diff --git a/src/network/network_coordinator.cpp b/src/network/network_coordinator.cpp
--- a/src/network/network_coordinator.cpp
+++ b/src/network/network_coordinator.cpp
@@ -19,6 +19,8 @@
 #include "network_coordinator.h"
 #include "network_gamelist.h"
 #include "network_internal.h"
+#include "network_server.h"
+#include "network_stun.h"
 #include "table/strings.h"
 
 #include "../safeguards.h"
@@ -51,7 +53,48 @@ public:
 
 	void OnConnect(SOCKET s) override
 	{
-		_network_coordinator_client.ConnectSuccess(this->token, s);
+		NetworkAddress address = NetworkAddress::GetPeerAddress(s);
+		_network_coordinator_client.ConnectSuccess(this->token, s, address);
+	}
+};
+
+/** Connecter used after STUN exchange to connect from both sides to each other. */
+class NetworkReuseStunConnecter : public TCPConnecter {
+private:
+	std::string token;     ///< Token of this connection.
+	uint8 tracking_number; ///< Tracking number of this connection.
+	uint8 family;          ///< Family of this connection.
+
+public:
+	/**
+	 * Try to establish a STUN-based connection.
+	 * @param hostname The hostname of the peer.
+	 * @param port The port of the peer.
+	 * @param bind_address The local bind address used for this connection.
+	 * @param token The connection token.
+	 * @param tracking_number The tracking number of the connection.
+	 * @param family The family this connection is using.
+	 */
+	NetworkReuseStunConnecter(const std::string &hostname, uint16 port, const NetworkAddress &bind_address, std::string token, uint8 tracking_number, uint8 family) :
+		TCPConnecter(hostname, port, bind_address),
+		token(token),
+		tracking_number(tracking_number),
+		family(family)
+	{
+	}
+
+	void OnFailure() override
+	{
+		/* Close the STUN connection too, as it is no longer of use. */
+		_network_coordinator_client.CloseStunHandler(this->token, this->family);
+
+		_network_coordinator_client.ConnectFailure(this->token, this->tracking_number);
+	}
+
+	void OnConnect(SOCKET s) override
+	{
+		NetworkAddress address = NetworkAddress::GetPeerAddress(s);
+		_network_coordinator_client.ConnectSuccess(this->token, s, address);
 	}
 };
 
@@ -101,10 +144,7 @@ bool ClientNetworkCoordinatorSocketHandl
 			return false;
 
 		case NETWORK_COORDINATOR_ERROR_INVALID_INVITE_CODE: {
-			/* Find the connecter based on the invite code. */
-			auto connecter_it = this->connecter_pre.find(detail);
-			if (connecter_it == this->connecter_pre.end()) return true;
-			this->connecter_pre.erase(connecter_it);
+			this->CloseToken(detail);
 
 			/* Mark the server as offline. */
 			NetworkGameList *item = NetworkGameListAddItem(detail);
@@ -148,6 +188,7 @@ bool ClientNetworkCoordinatorSocketHandl
 		switch (_network_server_connection_type) {
 			case CONNECTION_TYPE_ISOLATED: connection_type = "Remote players can't connect"; break;
 			case CONNECTION_TYPE_DIRECT:   connection_type = "Public"; break;
+			case CONNECTION_TYPE_STUN:     connection_type = "Behind NAT"; break;
 
 			case CONNECTION_TYPE_UNKNOWN: // Never returned from Game Coordinator.
 			default: connection_type = "Unknown"; break; // Should never happen, but don't fail if it does.
@@ -263,6 +304,49 @@ bool ClientNetworkCoordinatorSocketHandl
 	return true;
 }
 
+bool ClientNetworkCoordinatorSocketHandler::Receive_GC_STUN_REQUEST(Packet *p)
+{
+	std::string token = p->Recv_string(NETWORK_TOKEN_LENGTH);
+
+	this->stun_handlers[token][AF_INET6] = ClientNetworkStunSocketHandler::Stun(token, AF_INET6);
+	this->stun_handlers[token][AF_INET] = ClientNetworkStunSocketHandler::Stun(token, AF_INET);
+	return true;
+}
+
+bool ClientNetworkCoordinatorSocketHandler::Receive_GC_STUN_CONNECT(Packet *p)
+{
+	std::string token = p->Recv_string(NETWORK_TOKEN_LENGTH);
+	uint8 tracking_number = p->Recv_uint8();
+	uint8 family = p->Recv_uint8();
+	std::string host = p->Recv_string(NETWORK_HOSTNAME_PORT_LENGTH);
+	uint16 port = p->Recv_uint16();
+
+	/* Check if we know this token. */
+	auto stun_it = this->stun_handlers.find(token);
+	if (stun_it == this->stun_handlers.end()) return true;
+	auto family_it = stun_it->second.find(family);
+	if (family_it == stun_it->second.end()) return true;
+
+	/* Ensure all other pending connection attempts are killed. */
+	if (this->game_connecter != nullptr) {
+		this->game_connecter->Kill();
+		this->game_connecter = nullptr;
+	}
+
+	/* We now mark the connection as closed, but we do not really close the
+	 * socket yet. We do this when the NetworkReuseStunConnecter is connected.
+	 * This prevents any NAT to already remove the route while we create the
+	 * second connection on top of the first. */
+	family_it->second->CloseConnection(false);
+
+	/* Connect to our peer from the same local address as we use for the
+	 * STUN server. This means that if there is any NAT in the local network,
+	 * the public ip:port is still pointing to the local address, and as such
+	 * a connection can be established. */
+	this->game_connecter = new NetworkReuseStunConnecter(host, port, family_it->second->local_addr, token, tracking_number, family);
+	return true;
+}
+
 void ClientNetworkCoordinatorSocketHandler::Connect()
 {
 	/* We are either already connected or are trying to connect. */
@@ -399,11 +483,8 @@ void ClientNetworkCoordinatorSocketHandl
 
 	this->SendPacket(p);
 
-	auto connecter_it = this->connecter.find(token);
-	assert(connecter_it != this->connecter.end());
-
-	connecter_it->second->SetFailure();
-	this->connecter.erase(connecter_it);
+	/* We do not close the associated connecter here yet, as the
+	 * Game Coordinator might have other methods of connecting available. */
 }
 
 /**
@@ -412,29 +493,75 @@ void ClientNetworkCoordinatorSocketHandl
  * @param token Token of the connecter that succeeded.
  * @param sock The socket that the connecter can now use.
  */
-void ClientNetworkCoordinatorSocketHandler::ConnectSuccess(const std::string &token, SOCKET sock)
+void ClientNetworkCoordinatorSocketHandler::ConnectSuccess(const std::string &token, SOCKET sock, NetworkAddress &address)
 {
 	/* Connecter will destroy itself. */
 	this->game_connecter = nullptr;
 
-	assert(!_network_server);
+	if (_network_server) {
+		if (!ServerNetworkGameSocketHandler::ValidateClient(sock, address)) return;
+		Debug(net, 3, "[{}] Client connected from {} on frame {}", ServerNetworkGameSocketHandler::GetName(), address.GetHostname(), _frame_counter);
+		ServerNetworkGameSocketHandler::AcceptConnection(sock, address);
+	} else {
+		/* The client informs the Game Coordinator about the success. The server
+		 * doesn't have to, as it is implied by the client telling. */
+		Packet *p = new Packet(PACKET_COORDINATOR_CLIENT_CONNECTED);
+		p->Send_uint8(NETWORK_COORDINATOR_VERSION);
+		p->Send_string(token);
+		this->SendPacket(p);
 
-	Packet *p = new Packet(PACKET_COORDINATOR_CLIENT_CONNECTED);
-	p->Send_uint8(NETWORK_COORDINATOR_VERSION);
-	p->Send_string(token);
-	this->SendPacket(p);
+		auto connecter_it = this->connecter.find(token);
+		assert(connecter_it != this->connecter.end());
 
-	auto connecter_it = this->connecter.find(token);
-	assert(connecter_it != this->connecter.end());
-
-	connecter_it->second->SetConnected(sock);
-	this->connecter.erase(connecter_it);
+		connecter_it->second->SetConnected(sock);
+		this->connecter.erase(connecter_it);
+	}
 
 	/* Close all remaining connections. */
 	this->CloseToken(token);
 }
 
 /**
+ * Callback from the STUN connecter to inform the Game Coordinator about the
+ * result of the STUN.
+ *
+ * This helps the Game Coordinator not to wait for a timeout on its end, but
+ * rather react as soon as the client/server knows the result.
+ */
+void ClientNetworkCoordinatorSocketHandler::StunResult(const std::string &token, uint8 family, bool result)
+{
+	Packet *p = new Packet(PACKET_COORDINATOR_SERCLI_STUN_RESULT);
+	p->Send_uint8(NETWORK_COORDINATOR_VERSION);
+	p->Send_string(token);
+	p->Send_uint8(family);
+	p->Send_bool(result);
+	this->SendPacket(p);
+}
+
+void ClientNetworkCoordinatorSocketHandler::CloseStunHandler(const std::string &token, uint8 family)
+{
+	auto stun_it = this->stun_handlers.find(token);
+	if (stun_it == this->stun_handlers.end()) return;
+
+	if (family == AF_UNSPEC) {
+		for (auto &[family, stun_handler] : stun_it->second) {
+			stun_handler->CloseConnection();
+			stun_handler->CloseSocket();
+		}
+
+		this->stun_handlers.erase(stun_it);
+	} else {
+		auto family_it = stun_it->second.find(family);
+		if (family_it == stun_it->second.end()) return;
+
+		family_it->second->CloseConnection();
+		family_it->second->CloseSocket();
+
+		stun_it->second.erase(family_it);
+	}
+}
+
+/**
  * Close everything related to this connection token.
  * @param token The connection token to close.
  */
@@ -445,6 +572,21 @@ void ClientNetworkCoordinatorSocketHandl
 		this->game_connecter->Kill();
 		this->game_connecter = nullptr;
 	}
+
+	/* Close all remaining STUN connections. */
+	this->CloseStunHandler(token);
+
+	/* Close the caller of the connection attempt. */
+	auto connecter_it = this->connecter.find(token);
+	if (connecter_it != this->connecter.end()) {
+		connecter_it->second->SetFailure();
+		this->connecter.erase(connecter_it);
+	}
+	auto connecter_pre_it = this->connecter_pre.find(token);
+	if (connecter_pre_it != this->connecter_pre.end()) {
+		connecter_pre_it->second->SetFailure();
+		this->connecter_pre.erase(connecter_pre_it);
+	}
 }
 
 /**
@@ -460,6 +602,7 @@ void ClientNetworkCoordinatorSocketHandl
 
 	/* Mark any pending connecters as failed. */
 	for (auto &[token, it] : this->connecter) {
+		this->CloseStunHandler(token);
 		it->SetFailure();
 	}
 	for (auto &[invite_code, it] : this->connecter_pre) {
@@ -535,4 +678,10 @@ void ClientNetworkCoordinatorSocketHandl
 	}
 
 	this->SendPackets();
+
+	for (const auto &[token, families] : this->stun_handlers) {
+		for (const auto &[family, stun_handler] : families) {
+			stun_handler->SendReceive();
+		}
+	}
 }
diff --git a/src/network/network_coordinator.h b/src/network/network_coordinator.h
--- a/src/network/network_coordinator.h
+++ b/src/network/network_coordinator.h
@@ -11,6 +11,7 @@
 #define NETWORK_COORDINATOR_H
 
 #include "core/tcp_coordinator.h"
+#include "network_stun.h"
 #include <map>
 
 /**
@@ -33,6 +34,12 @@
  *        - Send the client a GC_CONNECT with the peer address.
  *        - a) Client connects, client sends CLIENT_CONNECTED to Game Coordinator.
  *        - b) Client connect fails, client sends CLIENT_CONNECT_FAILED to Game Coordinator.
+ *    2) STUN? (see https://en.wikipedia.org/wiki/STUN)
+ *        - Game Coordinator sends GC_STUN_REQUEST to server/client (asking for both IPv4 and IPv6 STUN requests).
+ *        - Game Coordinator collects what combination works and sends GC_STUN_CONNECT to server/client.
+ *        - a) Server/client connect, client sends CLIENT_CONNECTED to Game Coordinator.
+ *        - b) Server/client connect fails, both send SERCLI_CONNECT_FAILED to Game Coordinator.
+ *        - Game Coordinator tries other combination if available.
  *  - If all fails, Game Coordinator sends GC_CONNECT_FAILED to indicate no connection is possible.
  */
 
@@ -42,6 +49,7 @@ private:
 	std::chrono::steady_clock::time_point next_update; ///< When to send the next update (if server and public).
 	std::map<std::string, TCPServerConnecter *> connecter; ///< Based on tokens, the current connecters that are pending.
 	std::map<std::string, TCPServerConnecter *> connecter_pre; ///< Based on invite codes, the current connecters that are pending.
+	std::map<std::string, std::map<int, std::unique_ptr<ClientNetworkStunSocketHandler>>> stun_handlers; ///< All pending STUN handlers, stored by token:family.
 	TCPConnecter *game_connecter = nullptr; ///< Pending connecter to the game server.
 
 protected:
@@ -51,6 +59,8 @@ protected:
 	bool Receive_GC_CONNECTING(Packet *p) override;
 	bool Receive_GC_CONNECT_FAILED(Packet *p) override;
 	bool Receive_GC_DIRECT_CONNECT(Packet *p) override;
+	bool Receive_GC_STUN_REQUEST(Packet *p) override;
+	bool Receive_GC_STUN_CONNECT(Packet *p) override;
 
 public:
 	/** The idle timeout; when to close the connection because it's idle. */
@@ -65,11 +75,13 @@ public:
 	void SendReceive();
 
 	void ConnectFailure(const std::string &token, uint8 tracking_number);
-	void ConnectSuccess(const std::string &token, SOCKET sock);
+	void ConnectSuccess(const std::string &token, SOCKET sock, NetworkAddress &address);
+	void StunResult(const std::string &token, uint8 family, bool result);
 
 	void Connect();
 	void CloseToken(const std::string &token);
 	void CloseAllTokens();
+	void CloseStunHandler(const std::string &token, uint8 family = AF_UNSPEC);
 
 	void Register();
 	void SendServerUpdate();
diff --git a/src/network/network_stun.cpp b/src/network/network_stun.cpp
new file mode 100644
--- /dev/null
+++ b/src/network/network_stun.cpp
@@ -0,0 +1,140 @@
+/*
+ * This file is part of OpenTTD.
+ * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
+ * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/** @file network_stun.cpp STUN sending/receiving part of the network protocol. */
+
+#include "../stdafx.h"
+#include "../debug.h"
+#include "network.h"
+#include "network_coordinator.h"
+#include "network_stun.h"
+
+#include "../safeguards.h"
+
+/** Connect to the STUN server. */
+class NetworkStunConnecter : public TCPConnecter {
+private:
+	ClientNetworkStunSocketHandler *stun_handler;
+	std::string token;
+	uint8 family;
+
+public:
+	/**
+	 * Initiate the connecting.
+	 * @param stun_handler The handler for this request.
+	 * @param connection_string The address of the server.
+	 */
+	NetworkStunConnecter(ClientNetworkStunSocketHandler *stun_handler, const std::string &connection_string, const std::string &token, uint8 family) :
+		TCPConnecter(connection_string, NETWORK_STUN_SERVER_PORT, NetworkAddress(), family),
+		stun_handler(stun_handler),
+		token(token),
+		family(family)
+	{
+	}
+
+	void OnFailure() override
+	{
+		this->stun_handler->connecter = nullptr;
+
+		/* Connection to STUN server failed. For example, the client doesn't
+		 * support IPv6, which means it will fail that attempt. */
+
+		_network_coordinator_client.StunResult(this->token, this->family, false);
+	}
+
+	void OnConnect(SOCKET s) override
+	{
+		this->stun_handler->connecter = nullptr;
+
+		assert(this->stun_handler->sock == INVALID_SOCKET);
+		this->stun_handler->sock = s;
+
+		/* Store the local address; later connects will reuse it again.
+		 * This is what makes STUN work for most NATs. */
+		this->stun_handler->local_addr = NetworkAddress::GetSockAddress(s);
+
+		/* We leave the connection open till the real connection is setup later. */
+	}
+};
+
+/**
+ * Connect to the STUN server over either IPv4 or IPv6.
+ * @param token The token as received from the Game Coordinator.
+ * @param family What IP family to use.
+ */
+void ClientNetworkStunSocketHandler::Connect(const std::string &token, uint8 family)
+{
+	this->token = token;
+	this->family = family;
+
+	this->connecter = new NetworkStunConnecter(this, NetworkStunConnectionString(), token, family);
+}
+
+/**
+ * Send a STUN packet to the STUN server.
+ * @param token The token as received from the Game Coordinator.
+ * @param family What IP family this STUN request is for.
+ * @return The handler for this STUN request.
+ */
+std::unique_ptr<ClientNetworkStunSocketHandler> ClientNetworkStunSocketHandler::Stun(const std::string &token, uint8 family)
+{
+	auto stun_handler = std::make_unique<ClientNetworkStunSocketHandler>();
+
+	stun_handler->Connect(token, family);
+
+	Packet *p = new Packet(PACKET_STUN_SERCLI_STUN);
+	p->Send_uint8(NETWORK_COORDINATOR_VERSION);
+	p->Send_string(token);
+	p->Send_uint8(family);
+
+	stun_handler->SendPacket(p);
+
+	return stun_handler;
+}
+
+NetworkRecvStatus ClientNetworkStunSocketHandler::CloseConnection(bool error)
+{
+	NetworkStunSocketHandler::CloseConnection(error);
+
+	/* If our connecter is still pending, shut it down too. Otherwise the
+	 * callback of the connecter can call into us, and our object is most
+	 * likely about to be destroyed. */
+	if (this->connecter != nullptr) {
+		this->connecter->Kill();
+		this->connecter = nullptr;
+	}
+
+	return NETWORK_RECV_STATUS_OKAY;
+}
+
+/**
+ * Check whether we received/can send some data from/to the STUN server and
+ * when that's the case handle it appropriately.
+ */
+void ClientNetworkStunSocketHandler::SendReceive()
+{
+	if (this->sock == INVALID_SOCKET) return;
+
+	/* We never attempt to receive anything on a STUN socket. After
+	 * connecting a STUN connection, the local address will be reused to
+	 * to establish the connection with the real server. If we would be to
+	 * read this socket, some OSes get confused and deliver us packets meant
+	 * for the real connection. It appears most OSes play best when we simply
+	 * never attempt to read it to start with (and the packets will remain
+	 * available on the other socket).
+	 * Protocol-wise, the STUN server will never send any packet back anyway. */
+
+	this->CanSendReceive();
+	if (this->SendPackets() == SPS_ALL_SENT && !this->sent_result) {
+		/* We delay giving the GC the result this long, as to make sure we
+		 * have sent the STUN packet first. This means the GC is more likely
+		 * to have the result ready by the time our StunResult() packet
+		 * arrives. */
+		this->sent_result = true;
+		_network_coordinator_client.StunResult(this->token, this->family, true);
+	}
+}
diff --git a/src/network/network_stun.h b/src/network/network_stun.h
new file mode 100644
--- /dev/null
+++ b/src/network/network_stun.h
@@ -0,0 +1,34 @@
+/*
+ * This file is part of OpenTTD.
+ * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
+ * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/** @file network_stun.h Part of the network protocol handling STUN requests. */
+
+#ifndef NETWORK_STUN_H
+#define NETWORK_STUN_H
+
+#include "core/tcp_stun.h"
+
+/** Class for handling the client side of the STUN connection. */
+class ClientNetworkStunSocketHandler : public NetworkStunSocketHandler {
+private:
+	std::string token;        ///< Token of this STUN handler.
+	uint8 family = AF_UNSPEC; ///< Family of this STUN handler.
+	bool sent_result = false; ///< Did we sent the result of the STUN connection?
+
+public:
+	TCPConnecter *connecter = nullptr; ///< Connecter instance.
+	NetworkAddress local_addr;         ///< Local addresses of the socket.
+
+	NetworkRecvStatus CloseConnection(bool error = true) override;
+	void SendReceive();
+
+	void Connect(const std::string &token, uint8 family);
+
+	static std::unique_ptr<ClientNetworkStunSocketHandler> Stun(const std::string &token, uint8 family);
+};
+
+#endif /* NETWORK_STUN_H */