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 18c1a2d6bf..1d235ecb1c 100644
--- a/tools/libxl/libxl.h
+++ b/tools/libxl/libxl.h
@@ -2657,6 +2657,8 @@ static inline int libxl_qemu_monitor_command_0x041200(libxl_ctx *ctx,
 
 #include <libxl_event.h>
 
+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..5349defcf0 100644
--- a/tools/libxl/libxl_domain.c
+++ b/tools/libxl/libxl_domain.c
@@ -1268,6 +1268,208 @@ 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 bool libxl__read_recent(FILE *f, unsigned long *sec,
+                               unsigned int *domid)
+{
+    int n;
+
+    assert(f);
+
+    n = fscanf(f, "%lu %u", sec, domid);
+    if (n == EOF)
+        return false;
+    else if (n != 2) /* malformed entry */
+        *domid = INVALID_DOMID;
+
+    return true;
+}
+
+static bool libxl__write_recent(FILE *f, unsigned long sec,
+                                unsigned int domid)
+{
+    assert(f);
+    assert(libxl_domid_valid_guest(domid));
+
+    return fprintf(f, "%lu %u\n", sec, domid) > 0;
+}
+
+static int libxl__mark_domid_recent(libxl__gc *gc, uint32_t domid)
+{
+    long timeout = libxl__get_domid_reuse_timeout();
+    libxl__flock *lock;
+    char *old, *new;
+    FILE *of = NULL, *nf = NULL;
+    struct timespec ts;
+    int rc = ERROR_FAIL;
+
+    lock = libxl__lock_domid_history(gc);
+    if (!lock) {
+        LOGED(ERROR, domid, "failed to acquire lock");
+        goto out;
+    }
+
+    old = libxl__domid_history_path(gc, NULL);
+    of = fopen(old, "r");
+    if (!of && errno != ENOENT)
+        LOGED(WARN, domid, "failed to open '%s'", old);
+
+    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;
+    }
+
+    if (of) {
+        unsigned long sec;
+        unsigned int val;
+
+        while (libxl__read_recent(of, &sec, &val)) {
+            if (!libxl_domid_valid_guest(val))
+                continue; /* Ignore invalid entries */
+
+            if (ts.tv_sec - sec > timeout)
+                continue; /* Ignore expired entries */
+
+            if (!libxl__write_recent(nf, sec, val)) {
+                LOGED(ERROR, domid, "failed to write to '%s'", new);
+                goto out;
+            }
+        }
+        if (ferror(of)) {
+            LOGED(ERROR, domid, "failed to read from '%s'", old);
+            goto out;
+        }
+    }
+
+    if (!libxl__write_recent(nf, ts.tv_sec, domid)) {
+        LOGED(ERROR, domid, "failed to write to '%s'", new);
+        goto out;
+    }
+
+    if (fclose(nf) == EOF) {
+        LOGED(ERROR, domid, "failed to close '%s'", new);
+        nf = NULL;
+        goto out;
+    }
+    nf = NULL;
+
+    if (of && fclose(of) == EOF) {
+        LOGED(ERROR, domid, "failed to close '%s'", old);
+        of = NULL;
+        goto out;
+    }
+    of = NULL;
+
+    if (rename(new, old) < 0) {
+        LOGED(ERROR, domid, "failed to rename '%s' -> '%s'", old, new);
+        goto out;
+    }
+    rc = 0;
+
+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();
+    const char *name;
+    FILE *f;
+    struct timespec ts;
+    unsigned long sec;
+    unsigned int val;
+    int rc = ERROR_FAIL;
+
+    name = GCSPRINTF("%s/domid-history", libxl__run_dir_path());
+    f = fopen(name, "r");
+    if (!f) {
+        if (errno != ENOENT)
+            LOGED(WARN, domid, "failed to open %s", name);
+        else
+            rc = 0;
+
+        goto out;
+    }
+
+    if (clock_gettime(CLOCK_MONOTONIC, &ts)) {
+        LOGED(ERROR, domid, "failed to get time");
+        goto out;
+    }
+
+    *recent = false;
+    while (libxl__read_recent(f, &sec, &val)) {
+        if (!libxl_domid_valid_guest(val))
+            continue; /* Ignore invalid entries */
+
+        if (val == domid && ts.tv_sec - sec <= timeout) {
+            *recent = true;
+            break;
+        }
+    }
+    if (ferror(f)) {
+        LOGED(ERROR, domid, "failed to read from '%s'", name);
+        goto out;
+    }
+
+    if (fclose(f) == EOF) {
+        LOGED(ERROR, domid, "failed to close '%s'", name);
+        f = NULL;
+        goto out;
+    }
+    f = NULL;
+    rc = 0;
+
+out:
+    if (f) fclose(f);
+    return rc;
+}
+
 static void devices_destroy_cb(libxl__egc *egc,
                                libxl__devices_remove_state *drs,
                                int rc)
@@ -1331,6 +1533,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 dd3c08bc14..39de2d5910 100644
--- a/tools/libxl/libxl_internal.h
+++ b/tools/libxl/libxl_internal.h
@@ -4260,6 +4260,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.
@@ -4658,6 +4660,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
@@ -4796,6 +4799,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
 
 /*
