Just received this message from Soren Johnson (Civ4 Lead Designer) regarding Civ4 multiplayer connectivity: If you are encountering problems when connecting to multiplayer games over the internet, chances are strong that you are not the cause of the problem. It is likely that players running firewall software that rejects incoming connection attempts may have already joined the game. Since these players do not have their firewall configured correctly, their computers are rejecting your attempt to connect. Therefore, it is vital that all players who wish to play multiplayer games ensure that their firewall is set up to allow Civilization IV to construct the necessary peer-to-peer network. If you are running firewall software, please verify that CivilizationIV.exe is listed on the "Exception List" of your firewall, and that incoming messages will be accepted for this process. If your firewall software does not offer an exception list, please open port 2056 for UDP traffic on your firewall. This will allow the required traffic through. Although Civilization IV contains logic to negotiate around many firewalls and NAT devices (routers), it can run into trouble under certain circumstances. The solution Civilization IV employs works with a vast majority of routers, but does not work with all brands. Very old models may have more problems than newer ones. Additionally, Civilization IV will have problems negotiating through 2 levels of network address translation (ie. a router behind a router). Also, negotiation may fail if you or an existing peer is running the game on a very large and busy LAN.