diff --git a/tools/libxl/libxl.h b/tools/libxl/libxl.h
index 80ae110a52..35e13428b2 100644
--- a/tools/libxl/libxl.h
+++ b/tools/libxl/libxl.h
@@ -1268,6 +1268,14 @@ void libxl_mac_copy(libxl_ctx *ctx, libxl_mac *dst, const libxl_mac *src);
  */
 #define LIBXL_HAVE_DOMAIN_NEED_MEMORY_CONFIG
 
+/*
+ * LIBXL_HAVE_CREATEINFO_DOMID
+ *
+ * libxl_domain_create_new() and libxl_domain_create_restore() will use
+ * a domid specified in libxl_domain_create_info().
+ */
+#define LIBXL_HAVE_CREATEINFO_DOMID
+
 typedef char **libxl_string_list;
 void libxl_string_list_dispose(libxl_string_list *sl);
 int libxl_string_list_length(const libxl_string_list *sl);
@@ -1528,6 +1536,7 @@ int libxl_ctx_free(libxl_ctx *ctx /* 0 is OK */);
 /* domain related functions */
 
 #define INVALID_DOMID ~0
+#define RANDOM_DOMID (INVALID_DOMID - 1)
 
 /* If the result is ERROR_ABORTED, the domain may or may not exist
  * (in a half-created state).  *domid will be valid and will be the
diff --git a/tools/libxl/libxl_create.c b/tools/libxl/libxl_create.c
index 3a7364e2ac..ccc9e70990 100644
--- a/tools/libxl/libxl_create.c
+++ b/tools/libxl/libxl_create.c
@@ -600,11 +600,77 @@ int libxl__domain_make(libxl__gc *gc, libxl_domain_config *d_config,
             goto out;
         }
 
-        ret = xc_domain_create(ctx->xch, domid, &create);
-        if (ret < 0) {
-            LOGED(ERROR, *domid, "domain creation fail");
-            rc = ERROR_FAIL;
-            goto out;
+        for (;;) {
+            uint32_t local_domid;
+            bool recent;
+
+            if (info->domid == RANDOM_DOMID) {
+                uint16_t v;
+
+                ret = libxl__random_bytes(gc, (void *)&v, sizeof(v));
+                if (ret < 0)
+                    break;
+
+                v &= DOMID_MASK;
+                if (!libxl_domid_valid_guest(v))
+                    continue;
+
+                local_domid = v;
+            } else {
+                local_domid = info->domid; /* May not be valid */
+            }
+
+            ret = xc_domain_create(ctx->xch, &local_domid, &create);
+            if (ret < 0) {
+                /*
+                 * If we generated a random domid and creation failed
+                 * because that domid already exists then simply try
+                 * again.
+                 */
+                if (errno == EEXIST && info->domid == RANDOM_DOMID)
+                    continue;
+
+                LOGED(ERROR, local_domid, "domain creation fail");
+                rc = ERROR_FAIL;
+                goto out;
+            }
+
+            /* A new domain now exists */
+            *domid = local_domid;
+
+            rc = libxl__is_domid_recent(gc, local_domid, &recent);
+            if (rc)
+                goto out;
+
+            /* The domid is not recent, so we're done */
+            if (!recent)
+                break;
+
+            /*
+             * If the domid was specified then there's no point in
+             * trying again.
+             */
+            if (libxl_domid_valid_guest(info->domid)) {
+                LOGED(ERROR, local_domid, "domain id recently used");
+                rc = ERROR_FAIL;
+                goto out;
+            }
+
+            /*
+             * The domain is recent and so cannot be used. Clear domid
+             * here since, if xc_domain_destroy() fails below there is
+             * little point calling it again in the error path.
+             */
+            *domid = INVALID_DOMID;
+
+            ret = xc_domain_destroy(ctx->xch, local_domid);
+            if (ret < 0) {
+                LOGED(ERROR, local_domid, "domain destroy fail");
+                rc = ERROR_FAIL;
+                goto out;
+            }
+
+            /* The domain was successfully destroyed, so we can try again */
         }
 
         rc = libxl__arch_domain_save_config(gc, d_config, state, &create);
diff --git a/tools/libxl/libxl_types.idl b/tools/libxl/libxl_types.idl
index 7921950f6a..d0d431614f 100644
--- a/tools/libxl/libxl_types.idl
+++ b/tools/libxl/libxl_types.idl
@@ -409,6 +409,7 @@ libxl_domain_create_info = Struct("domain_create_info",[
     ("ssidref",      uint32),
     ("ssid_label",   string),
     ("name",         string),
+    ("domid",        libxl_domid),
     ("uuid",         libxl_uuid),
     ("xsdata",       libxl_key_value_list),
     ("platformdata", libxl_key_value_list),
