diff --git a/tools/helpers/xen-init-dom0.c b/tools/helpers/xen-init-dom0.c
index a1e5729458..56f69ab66f 100644
--- a/tools/helpers/xen-init-dom0.c
+++ b/tools/helpers/xen-init-dom0.c
@@ -12,6 +12,32 @@
 #define DOMNAME_PATH   "/local/domain/0/name"
 #define DOMID_PATH     "/local/domain/0/domid"
 
+int clear_domid_history(void)
+{
+    int rc = 1;
+    xentoollog_logger_stdiostream *logger;
+    libxl_ctx *ctx;
+
+    logger = xtl_createlogger_stdiostream(stderr, XTL_ERROR, 0);
+    if (!logger)
+        return 1;
+
+    if (libxl_ctx_alloc(&ctx, LIBXL_VERSION, 0,
+                        (xentoollog_logger *)logger)) {
+        fprintf(stderr, "cannot init libxl context\n");
+        goto outlog;
+    }
+
+    if (!libxl_clear_domid_history(ctx))
+        rc = 0;
+
+    libxl_ctx_free(ctx);
+
+outlog:
+    xtl_logger_destroy((xentoollog_logger *)logger);
+    return rc;
+}
+
 int main(int argc, char **argv)
 {
     int rc;
@@ -70,6 +96,10 @@ int main(int argc, char **argv)
     if (rc)
         goto out;
 
+    rc = clear_domid_history();
+    if (rc)
+        goto out;
+
     /* Write xenstore entries. */
     if (!xs_write(xsh, XBT_NULL, DOMID_PATH, "0", strlen("0"))) {
         fprintf(stderr, "cannot set domid for Dom0\n");
diff --git a/tools/libxl/libxl.h b/tools/libxl/libxl.h
index fde8548847..80ae110a52 100644
--- a/tools/libxl/libxl.h
+++ b/tools/libxl/libxl.h
@@ -2679,6 +2679,13 @@ static inline int libxl_qemu_monitor_command_0x041200(libxl_ctx *ctx,
 
 #include <libxl_event.h>
 
+/*
+ * This function is for use only during host initialisation. If it is
+ * invoked on a host with running domains, or concurrent libxl
+ * processes then the system may malfuntion.
+ */
+int libxl_clear_domid_history(libxl_ctx *ctx);
+
 #endif /* LIBXL_H */
 
 /*
diff --git a/tools/libxl/libxl_domain.c b/tools/libxl/libxl_domain.c
index 973fc1434d..53f90cb555 100644
--- a/tools/libxl/libxl_domain.c
+++ b/tools/libxl/libxl_domain.c
@@ -1268,6 +1268,226 @@ static void dm_destroy_cb(libxl__egc *egc,
     libxl__devices_destroy(egc, &dis->drs);
 }
 
+static unsigned int libxl__get_domid_reuse_timeout(void)
+{
+    const char *env_timeout = getenv("LIBXL_DOMID_REUSE_TIMEOUT");
+
+    return env_timeout ? strtol(env_timeout, NULL, 0) :
+        LIBXL_DOMID_REUSE_TIMEOUT;
+}
+
+char *libxl__domid_history_path(libxl__gc *gc, const char *suffix)
+{
+    return GCSPRINTF("%s/domid-history%s", libxl__run_dir_path(),
+                     suffix ?: "");
+}
+
+int libxl_clear_domid_history(libxl_ctx *ctx)
+{
+    GC_INIT(ctx);
+    char *path;
+    int rc = ERROR_FAIL;
+
+    path = libxl__domid_history_path(gc, NULL);
+    if (!path)
+        goto out;
+
+    if (unlink(path) < 0 && errno != ENOENT) {
+        LOGE(ERROR, "failed to remove '%s'\n", path);
+        goto out;
+    }
+
+    rc = 0;
+
+out:
+    GC_FREE;
+    return rc;
+}
+
+static int libxl__read_recent(libxl__gc *gc, FILE *f, unsigned long *sec,
+                              unsigned int *domid)
+{
+    if (!f) {
+        *domid = INVALID_DOMID;
+        return 0;
+    }
+
+    for (;;) {
+        int n = fscanf(f, "%lu %u", sec, domid);
+
+        if (n == EOF) {
+            if (ferror(f)) {
+                LOGE(ERROR, "failed");
+                return ERROR_FAIL;
+            }
+
+            *domid = INVALID_DOMID;
+            break;
+        } else if (n == 2 && libxl_domid_valid_guest(*domid)) {
+            break;
+        }
+    }
+
+    return 0;
+}
+
+static int libxl__write_recent(libxl__gc *gc, FILE *f, unsigned long sec,
+                               unsigned int domid)
+{
+    int n = fprintf(f, "%lu %u\n", sec, domid);
+
+    if (n >= 0) return 0;
+
+    LOGE(ERROR, "failed");
+    return ERROR_FAIL;
+}
+
+static int libxl__open_domid_history(libxl__gc *gc, FILE **f)
+{
+    char *path = libxl__domid_history_path(gc, NULL);
+
+    *f = fopen(path, "r");
+    if (*f || errno == ENOENT) return 0;
+
+    LOGE(ERROR, "failed to open '%s'", path);
+    return ERROR_FAIL;
+}
+
+static int libxl__close_domid_history(libxl__gc *gc, FILE **f)
+{
+    int ret;
+
+    if (!*f) return 0;
+
+    ret = fclose(*f);
+    *f = NULL;
+    if (!ret) return 0;
+
+    LOGE(ERROR, "failed");
+    return ERROR_FAIL;
+}
+
+static int libxl__replace_domid_history(libxl__gc *gc, char *new)
+{
+    char *path = libxl__domid_history_path(gc, NULL);
+    int ret = rename(new, path);
+
+    if (!ret) return 0;
+
+    LOGE(ERROR, "failed to rename '%s' -> '%s'", new, path);
+    return ERROR_FAIL;
+}
+
+static int libxl__mark_domid_recent(libxl__gc *gc, uint32_t domid)
+{
+    long timeout = libxl__get_domid_reuse_timeout();
+    libxl__flock *lock;
+    char *new;
+    FILE *of = NULL, *nf = NULL;
+    struct timespec ts;
+    int ret, rc;
+
+    lock = libxl__lock_domid_history(gc);
+    if (!lock) {
+        LOGED(ERROR, domid, "failed to acquire lock");
+        rc = ERROR_FAIL;
+        goto out;
+    }
+
+    rc = libxl__open_domid_history(gc, &of);
+    if (rc) goto out;
+
+    new = libxl__domid_history_path(gc, ".new");
+    nf = fopen(new, "a");
+    if (!nf) {
+        LOGED(ERROR, domid, "failed to open '%s'", new);
+        goto out;
+    }
+
+    if (clock_gettime(CLOCK_MONOTONIC, &ts)) {
+        LOGED(ERROR, domid, "failed to get time");
+        goto out;
+    }
+
+    for (;;) {
+        unsigned long sec;
+        unsigned int val;
+
+        rc = libxl__read_recent(gc, of, &sec, &val);
+        if (rc) goto out;
+
+        if (val == INVALID_DOMID) /* EOF */
+            break;
+
+        if (ts.tv_sec - sec > timeout)
+            continue; /* Ignore expired entries */
+
+        rc = libxl__write_recent(gc, nf, sec, val);
+        if (rc) goto out;
+    }
+
+    rc = libxl__write_recent(gc, nf, ts.tv_sec, domid);
+    if (rc) goto out;
+
+    ret = fclose(nf);
+    nf = NULL;
+    if (ret == EOF) {
+        LOGED(ERROR, domid, "failed to close '%s'", new);
+        goto out;
+    }
+
+    rc = libxl__close_domid_history(gc, &of);
+    if (rc) goto out;
+
+    rc = libxl__replace_domid_history(gc, new);
+
+out:
+    if (nf) fclose(nf);
+    if (of) fclose(of);
+    if (lock) libxl__unlock_file(lock);
+
+    return rc;
+}
+
+int libxl__is_domid_recent(libxl__gc *gc, uint32_t domid, bool *recent)
+{
+    long timeout = libxl__get_domid_reuse_timeout();
+    FILE *f;
+    struct timespec ts;
+    int rc;
+
+    rc = libxl__open_domid_history(gc, &f);
+    if (rc) goto out;
+
+    if (clock_gettime(CLOCK_MONOTONIC, &ts)) {
+        LOGED(ERROR, domid, "failed to get time");
+        goto out;
+    }
+
+    *recent = false;
+    for (;;) {
+        unsigned long sec;
+        unsigned int val;
+
+        rc = libxl__read_recent(gc, f, &sec, &val);
+        if (rc) goto out;
+
+        if (val == INVALID_DOMID) /* EOF */
+            break;
+
+        if (val == domid && ts.tv_sec - sec <= timeout) {
+            *recent = true;
+            break;
+        }
+    }
+
+    rc = libxl__close_domid_history(gc, &f);
+
+out:
+    if (f) fclose(f);
+    return rc;
+}
+
 static void devices_destroy_cb(libxl__egc *egc,
                                libxl__devices_remove_state *drs,
                                int rc)
@@ -1331,6 +1551,8 @@ static void devices_destroy_cb(libxl__egc *egc,
         if (!ctx->xch) goto badchild;
 
         if (!dis->soft_reset) {
+            rc = libxl__mark_domid_recent(gc, domid);
+            if (rc) goto badchild;
             rc = xc_domain_destroy(ctx->xch, domid);
         } else {
             rc = xc_domain_pause(ctx->xch, domid);
diff --git a/tools/libxl/libxl_internal.c b/tools/libxl/libxl_internal.c
index 211236dc99..bbd4c6cba9 100644
--- a/tools/libxl/libxl_internal.c
+++ b/tools/libxl/libxl_internal.c
@@ -504,6 +504,16 @@ libxl__flock *libxl__lock_domain_userdata(libxl__gc *gc, uint32_t domid)
     return lock;
 }
 
+libxl__flock *libxl__lock_domid_history(libxl__gc *gc)
+{
+    const char *lockfile;
+
+    lockfile = libxl__domid_history_path(gc, ".lock");
+    if (!lockfile) return NULL;
+
+    return libxl__lock_file(gc, lockfile);
+}
+
 int libxl__get_domain_configuration(libxl__gc *gc, uint32_t domid,
                                     libxl_domain_config *d_config)
 {
diff --git a/tools/libxl/libxl_internal.h b/tools/libxl/libxl_internal.h
index 4936446069..43e5885d1e 100644
--- a/tools/libxl/libxl_internal.h
+++ b/tools/libxl/libxl_internal.h
@@ -4263,6 +4263,8 @@ _hidden void libxl__remus_teardown(libxl__egc *egc,
 _hidden void libxl__remus_restore_setup(libxl__egc *egc,
                                         libxl__domain_create_state *dcs);
 
+_hidden char *libxl__domid_history_path(libxl__gc *gc,
+                                        const char *suffix);
 
 /*
  * Convenience macros.
@@ -4661,6 +4663,7 @@ libxl__flock *libxl__lock_file(libxl__gc *gc, const char *filename);
 void libxl__unlock_file(libxl__flock *lock);
 
 libxl__flock *libxl__lock_domain_userdata(libxl__gc *gc, uint32_t domid);
+libxl__flock *libxl__lock_domid_history(libxl__gc *gc);
 
 /*
  * Retrieve / store domain configuration from / to libxl private
@@ -4799,6 +4802,17 @@ _hidden int libxl__domain_pvcontrol(libxl__egc *egc,
                                     libxl__xswait_state *pvcontrol,
                                     domid_t domid, const char *cmd);
 
+/*
+ * Maximum number of seconds after desctruction then a domid remains
+ * 'recent'. Recent domids are not allowed to be re-used. This can be
+ * overidden, for debugging purposes, by the environment variable of the
+ * same name.
+ */
+#define LIBXL_DOMID_REUSE_TIMEOUT 60
+
+/* Check whether a domid is recent */
+int libxl__is_domid_recent(libxl__gc *gc, uint32_t domid, bool *recent);
+
 #endif
 
 /*
