diff --git a/src/or/connection.c b/src/or/connection.c
@@ -112,11 +112,33 @@
 #include <sys/un.h>
 #endif
 
+/**
+ * On Windows and Linux we cannot reliably bind() a socket to an
+ * address and port if: 1) There's already a socket bound to wildcard
+ * address (0.0.0.0 or ::) with the same port; 2) We try to bind()
+ * to wildcard address and there's another socket bound to a
+ * specific address and the same port.
+ *
+ * To address this problem on these two platforms we implement a
+ * routine that:
+ * 1) Checks if first attempt to bind() a new socket  failed with
+ * EADDRINUSE.
+ * 2) If so, it will close the appropriate old listener connection and
+ * 3) Attempts bind()'ing the new listener socket again.
+ */
+#if defined(__linux__) || defined(_WIN32)
+#define ENABLE_LISTENER_REBIND
+#endif
+
 static connection_t *connection_listener_new(
                                const struct sockaddr *listensockaddr,
                                socklen_t listensocklen, int type,
                                const char *address,
-                               const port_cfg_t *portcfg);
+                               const port_cfg_t *portcfg,
+                               int *addr_in_use);
+static connection_t *connection_listener_new_for_port(
+                               const port_cfg_t *port,
+                               int *defer, int *addr_in_use);
 static void connection_init(time_t now, connection_t *conn, int type,
                             int socket_family);
 static int connection_handle_listener_read(connection_t *conn, int new_type);
@@ -1141,12 +1163,16 @@ tor_listen(tor_socket_t fd)
  *
  * <b>address</b> is only used for logging purposes and to add the information
  * to the conn.
+ *
+ * Set <b>addr_in_use</b> to true in case socket binding fails with
+ * EADDRINUSE.
  */
 static connection_t *
 connection_listener_new(const struct sockaddr *listensockaddr,
                         socklen_t socklen,
                         int type, const char *address,
-                        const port_cfg_t *port_cfg)
+                        const port_cfg_t *port_cfg,
+                        int *addr_in_use)
 {
   listener_connection_t *lis_conn;
   connection_t *conn = NULL;
@@ -1162,6 +1188,9 @@ connection_listener_new(const struct sockaddr *listensockaddr,
   tor_addr_t addr;
   int exhaustion = 0;
 
+  if (addr_in_use)
+    *addr_in_use = 0;
+
   if (listensockaddr->sa_family == AF_INET ||
       listensockaddr->sa_family == AF_INET6) {
     int is_stream = (type != CONN_TYPE_AP_DNS_LISTENER);
@@ -1240,8 +1269,11 @@ connection_listener_new(const struct sockaddr *listensockaddr,
     if (bind(s,listensockaddr,socklen) < 0) {
       const char *helpfulhint = "";
       int e = tor_socket_errno(s);
-      if (ERRNO_IS_EADDRINUSE(e))
+      if (ERRNO_IS_EADDRINUSE(e)) {
         helpfulhint = ". Is Tor already running?";
+        if (addr_in_use)
+          *addr_in_use = 1;
+      }
       log_warn(LD_NET, "Could not bind to %s:%u: %s%s", address, usePort,
                tor_socket_strerror(e), helpfulhint);
       goto err;
@@ -1428,6 +1460,8 @@ connection_listener_new(const struct sockaddr *listensockaddr,
    */
   connection_check_oos(get_n_open_sockets(), 0);
 
+  log_notice(LD_NET, "Opened %s on %s",
+             conn_type_to_string(type), fmt_addrport(&addr, usePort));
   return conn;
 
  err:
@@ -1442,6 +1476,68 @@ connection_listener_new(const struct sockaddr *listensockaddr,
   return NULL;
 }
 
+/**
+ * Create a new listener connection for a given <b>port</b>. In case we
+ * cannot create listener now, but will be able later, set <b>defer</b>
+ * to true. If we cannot bind listening socket because address is already
+ * in use, set <b>addr_in_use</b> to true.
+ */
+static connection_t *
+connection_listener_new_for_port(const port_cfg_t *port,
+                                 int *defer, int *addr_in_use)
+{
+  connection_t *conn;
+  struct sockaddr *listensockaddr;
+  socklen_t listensocklen = 0;
+  char *address=NULL;
+  int real_port = port->port == CFG_AUTO_PORT ? 0 : port->port;
+  tor_assert(real_port <= UINT16_MAX);
+
+  defer = 0;
+  if (port->server_cfg.no_listen) {
+    if (defer)
+      *defer = 1;
+    return NULL;
+  }
+
+#ifndef _WIN32
+  /* We don't need to be root to create a UNIX socket, so defer until after
+   * setuid. */
+  const or_options_t *options = get_options();
+  if (port->is_unix_addr && !geteuid() && (options->User) &&
+      strcmp(options->User, "root")) {
+    if (defer)
+      *defer = 1;
+    return NULL;
+  }
+#endif /* !defined(_WIN32) */
+
+  if (port->is_unix_addr) {
+    listensockaddr = (struct sockaddr *)
+      create_unix_sockaddr(port->unix_addr,
+                           &address, &listensocklen);
+  } else {
+    listensockaddr = tor_malloc(sizeof(struct sockaddr_storage));
+    listensocklen = tor_addr_to_sockaddr(&port->addr,
+                                         real_port,
+                                         listensockaddr,
+                                         sizeof(struct sockaddr_storage));
+    address = tor_addr_to_str_dup(&port->addr);
+  }
+
+  if (listensockaddr) {
+    conn = connection_listener_new(listensockaddr, listensocklen,
+                                   port->type, address, port,
+                                   addr_in_use);
+    tor_free(listensockaddr);
+    tor_free(address);
+  } else {
+    conn = NULL;
+  }
+
+  return conn;
+}
+
 /** Do basic sanity checking on a newly received socket. Return 0
  * if it looks ok, else return -1.
  *
@@ -2558,19 +2654,27 @@ connection_read_proxy_handshake(connection_t *conn)
  *
  * Remove from <b>old_conns</b> every connection that has a corresponding
  * entry in <b>ports</b>.  Add to <b>new_conns</b> new every connection we
- * launch.
+ * launch. If we may need to perform socket rebind when creating new
+ * listener that replaces old one, create a <b>listener_replacement_t</b>
+ * struct for affected pair  and add it to <b>replacements</b>.
  *
  * If <b>control_listeners_only</b> is true, then we only open control
- * listeners, and we do not remove any noncontrol listeners from old_conns.
+ * listeners, and we do not remove any noncontrol listeners from
+ * old_conns.
  *
  * Return 0 on success, -1 on failure.
  **/
 static int
 retry_listener_ports(smartlist_t *old_conns,
                      const smartlist_t *ports,
                      smartlist_t *new_conns,
+                     smartlist_t *replacements,
                      int control_listeners_only)
 {
+#ifndef ENABLE_LISTENER_REBIND
+  (void)replacements;
+#endif
+
   smartlist_t *launch = smartlist_new();
   int r = 0;
 
@@ -2606,16 +2710,34 @@ retry_listener_ports(smartlist_t *old_conns,
           break;
         }
       } else {
-        int port_matches;
-        if (wanted->port == CFG_AUTO_PORT) {
-          port_matches = 1;
-        } else {
-          port_matches = (wanted->port == conn->port);
-        }
+        /* Numeric values of old and new port match exactly. */
+        const int port_matches_exact = (wanted->port == conn->port);
+        /* Ports match semantically - either their specific values
+           match exactly, or new port is 'auto'.
+         */
+        const int port_matches = (wanted->port == CFG_AUTO_PORT ||
+                                  port_matches_exact);
+
         if (port_matches && tor_addr_eq(&wanted->addr, &conn->addr)) {
           found_port = wanted;
           break;
         }
+#ifdef ENABLE_LISTENER_REBIND
+        const int may_need_rebind =
+          port_matches_exact & bool_neq(tor_addr_is_null(&wanted->addr),
+                                        tor_addr_is_null(&conn->addr));
+        if (replacements && may_need_rebind) {
+          listener_replacement_t *replacement =
+            tor_malloc(sizeof(listener_replacement_t));
+
+          replacement->old_conn = conn;
+          replacement->new_port = wanted;
+          smartlist_add(replacements, replacement);
+
+          SMARTLIST_DEL_CURRENT(launch, wanted);
+          SMARTLIST_DEL_CURRENT(old_conns, conn);
+        }
+#endif
       }
     } SMARTLIST_FOREACH_END(wanted);
 
@@ -2631,52 +2753,13 @@ retry_listener_ports(smartlist_t *old_conns,
 
   /* Now open all the listeners that are configured but not opened. */
   SMARTLIST_FOREACH_BEGIN(launch, const port_cfg_t *, port) {
-    struct sockaddr *listensockaddr;
-    socklen_t listensocklen = 0;
-    char *address=NULL;
-    connection_t *conn;
-    int real_port = port->port == CFG_AUTO_PORT ? 0 : port->port;
-    tor_assert(real_port <= UINT16_MAX);
-    if (port->server_cfg.no_listen)
-      continue;
+    int skip = 0;
+    connection_t *conn = connection_listener_new_for_port(port, &skip, NULL);
 
-#ifndef _WIN32
-    /* We don't need to be root to create a UNIX socket, so defer until after
-     * setuid. */
-    const or_options_t *options = get_options();
-    if (port->is_unix_addr && !geteuid() && (options->User) &&
-        strcmp(options->User, "root"))
-      continue;
-#endif /* !defined(_WIN32) */
-
-    if (port->is_unix_addr) {
-      listensockaddr = (struct sockaddr *)
-        create_unix_sockaddr(port->unix_addr,
-                             &address, &listensocklen);
-    } else {
-      listensockaddr = tor_malloc(sizeof(struct sockaddr_storage));
-      listensocklen = tor_addr_to_sockaddr(&port->addr,
-                                           real_port,
-                                           listensockaddr,
-                                           sizeof(struct sockaddr_storage));
-      address = tor_addr_to_str_dup(&port->addr);
-    }
-
-    if (listensockaddr) {
-      conn = connection_listener_new(listensockaddr, listensocklen,
-                                     port->type, address, port);
-      tor_free(listensockaddr);
-      tor_free(address);
-    } else {
-      conn = NULL;
-    }
-
-    if (!conn) {
+    if (conn && new_conns)
+      smartlist_add(new_conns, conn);
+    else if (!skip)
       r = -1;
-    } else {
-      if (new_conns)
-        smartlist_add(new_conns, conn);
-    }
   } SMARTLIST_FOREACH_END(port);
 
   smartlist_free(launch);
@@ -2688,17 +2771,16 @@ retry_listener_ports(smartlist_t *old_conns,
  * listeners who are not already open, and only close listeners we no longer
  * want.
  *
- * Add all old conns that should be closed to <b>replaced_conns</b>.
  * Add all new connections to <b>new_conns</b>.
  *
  * If <b>close_all_noncontrol</b> is true, then we only open control
  * listeners, and we close all other listeners.
  */
 int
-retry_all_listeners(smartlist_t *replaced_conns,
-                    smartlist_t *new_conns, int close_all_noncontrol)
+retry_all_listeners(smartlist_t *new_conns, int close_all_noncontrol)
 {
   smartlist_t *listeners = smartlist_new();
+  smartlist_t *replacements = smartlist_new();
   const or_options_t *options = get_options();
   int retval = 0;
   const uint16_t old_or_port = router_get_advertised_or_port(options);
@@ -2714,20 +2796,54 @@ retry_all_listeners(smartlist_t *replaced_conns,
   if (retry_listener_ports(listeners,
                            get_configured_ports(),
                            new_conns,
+                           replacements,
                            close_all_noncontrol) < 0)
     retval = -1;
 
+#ifdef ENABLE_LISTENER_REBIND
+  SMARTLIST_FOREACH_BEGIN(replacements, listener_replacement_t *, r) {
+    int addr_in_use = 0;
+    int skip = 0;
+
+    tor_assert(r->new_port);
+    tor_assert(r->old_conn);
+
+    connection_t *new_conn =
+     connection_listener_new_for_port(r->new_port, &skip, &addr_in_use);
+    connection_t *old_conn = r->old_conn;
+
+    if (skip)
+      continue;
+
+    connection_close_immediate(old_conn);
+    connection_mark_for_close(old_conn);
+
+    if (addr_in_use) {
+      new_conn = connection_listener_new_for_port(r->new_port,
+                                                  &skip, &addr_in_use);
+    }
+
+    tor_assert(new_conn);
+
+    smartlist_add(new_conns, new_conn);
+
+    log_notice(LD_NET, "Closed no-longer-configured %s on %s:%d "
+                       "(replaced by %s:%d)",
+               conn_type_to_string(old_conn->type), old_conn->address,
+               old_conn->port, new_conn->address, new_conn->port);
+
+    tor_free(r);
+    SMARTLIST_DEL_CURRENT(replacements, r);
+  } SMARTLIST_FOREACH_END(r);
+#endif
+
   /* Any members that were still in 'listeners' don't correspond to
    * any configured port.  Kill 'em. */
   SMARTLIST_FOREACH_BEGIN(listeners, connection_t *, conn) {
     log_notice(LD_NET, "Closing no-longer-configured %s on %s:%d",
                conn_type_to_string(conn->type), conn->address, conn->port);
-    if (replaced_conns) {
-      smartlist_add(replaced_conns, conn);
-    } else {
-      connection_close_immediate(conn);
-      connection_mark_for_close(conn);
-    }
+    connection_close_immediate(conn);
+    connection_mark_for_close(conn);
   } SMARTLIST_FOREACH_END(conn);
 
   smartlist_free(listeners);

diff --git a/src/or/connection.h b/src/or/connection.h
@@ -15,6 +15,17 @@
 /* XXXX For buf_datalen in inline function */
 #include "buffers.h"
 
+/**
+ * This struct associates an old listener connection to be replaced
+ * by new connection described by port configuration. Only used when
+ * moving listeners to/from wildcard IP address.
+ */
+typedef struct
+{
+  connection_t *old_conn; /* Old listener connection to be replaced */
+  const port_cfg_t *new_port; /* New port configuration */
+} listener_replacement_t;
+
 const char *conn_type_to_string(int type);
 const char *conn_state_to_string(int type, int state);
 int conn_listener_type_supports_af_unix(int type);
@@ -112,8 +123,7 @@ void log_failed_proxy_connection(connection_t *conn);
 int get_proxy_addrport(tor_addr_t *addr, uint16_t *port, int *proxy_type,
                        const connection_t *conn);
 
-int retry_all_listeners(smartlist_t *replaced_conns,
-                        smartlist_t *new_conns,
+int retry_all_listeners(smartlist_t *new_conns,
                         int close_all_noncontrol);
 
 void connection_mark_all_noncontrol_listeners(void);

diff --git a/src/or/main.c b/src/or/main.c
@@ -2220,7 +2220,7 @@ retry_listeners_callback(time_t now, const or_options_t *options)
   (void)now;
   (void)options;
   if (!net_is_disabled()) {
-    retry_all_listeners(NULL, NULL, 0);
+    retry_all_listeners(NULL, 0);
     return 60;
   }
   return PERIODIC_EVENT_NO_UPDATE;

diff --git a/src/test/include.am b/src/test/include.am
@@ -29,6 +29,7 @@ endif
 
 if USEPYTHON
 TESTSCRIPTS += src/test/test_ntor.sh src/test/test_hs_ntor.sh src/test/test_bt.sh
+TESTSCRIPTS += src/test/test_rebind.sh
 endif
 
 TESTS += src/test/test src/test/test-slow src/test/test-memwipe \
@@ -349,6 +350,8 @@ EXTRA_DIST += \
 	src/test/hs_indexes.py \
 	src/test/fuzz_static_testcases.sh \
 	src/test/slownacl_curve25519.py \
+	src/test/test_rebind.sh \
+	src/test/test_rebind.py \
 	src/test/zero_length_keys.sh \
 	src/test/test_keygen.sh \
 	src/test/test_key_expiration.sh \

diff --git a/src/test/test_rebind.py b/src/test/test_rebind.py
@@ -0,0 +1,64 @@
+import sys
+import subprocess
+import socket
+import os
+import time
+
+def try_connecting_to_socksport():
+    socks_socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
+    if socks_socket.connect_ex(('127.0.0.1', 9052)):
+        tor_process.terminate()
+        print 'FAIL'
+        sys.exit('Cannot connect to SOCKSPort')
+    socks_socket.close()
+
+def wait_for_log(s):
+    while True:
+        l = tor_process.stdout.readline()
+        if s in l:
+            return
+
+if not os.path.exists(sys.argv[1]):
+    sys.exit('ERROR: cannot find tor at %s' % sys.argv[1])
+
+tor_path = sys.argv[1]
+
+tor_process = subprocess.Popen([tor_path,
+                               '-ControlPort', '127.0.0.1:9053', 
+                               '-SOCKSPort', '127.0.0.1:9052',
+                               '-FetchServerDescriptors', '0'],
+                               stdout=subprocess.PIPE,
+                               stderr=subprocess.PIPE)
+
+if tor_process == None:
+    sys.exit('ERROR: running tor failed')
+
+if len(sys.argv) < 2:
+     sys.exit('Usage: %s <path-to-tor>' % sys.argv[0])
+
+wait_for_log('Opened Control listener on')
+
+try_connecting_to_socksport()
+
+control_socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
+if control_socket.connect_ex(('127.0.0.1', 9053)):
+    tor_process.terminate()
+    print 'FAIL'
+    sys.exit('Cannot connect to ControlPort')
+
+control_socket.sendall('AUTHENTICATE \r\n')
+control_socket.sendall('SETCONF SOCKSPort=0.0.0.0:9052\r\n')
+wait_for_log('Opened Socks listener')
+
+try_connecting_to_socksport()
+
+control_socket.sendall('SETCONF SOCKSPort=127.0.0.1:9052\r\n')
+wait_for_log('Opened Socks listener')
+
+try_connecting_to_socksport()
+
+control_socket.sendall('SIGNAL HALT\r\n')
+
+time.sleep(0.1)
+print 'OK'
+tor_process.terminate()
diff --git a/src/test/test_rebind.sh b/src/test/test_rebind.sh
@@ -0,0 +1,7 @@
+#!/bin/sh
+
+exitcode=0
+
+"${PYTHON:-python}" "${abs_top_srcdir:-.}/src/test/test_rebind.py" "${TESTING_TOR_BINARY}" || exitcode=1
+
+exit ${exitcode}