--- a/testing/marionette/driver.js
+++ b/testing/marionette/driver.js
@@ -18,17 +18,20 @@ Cu.import("chrome://marionette/content/a
 Cu.import("chrome://marionette/content/atom.js");
 const {
   browser,
   Context,
 } = Cu.import("chrome://marionette/content/browser.js", {});
 Cu.import("chrome://marionette/content/capture.js");
 Cu.import("chrome://marionette/content/cert.js");
 Cu.import("chrome://marionette/content/cookie.js");
-Cu.import("chrome://marionette/content/element.js");
+const {
+  element,
+  WebElement,
+} = Cu.import("chrome://marionette/content/element.js", {});
 const {
   ElementNotInteractableError,
   InsecureCertificateError,
   InvalidArgumentError,
   InvalidCookieDomainError,
   InvalidSelectorError,
   NoAlertOpenError,
   NoSuchFrameError,

--- a/testing/marionette/element.js
+++ b/testing/marionette/element.js
@@ -68,19 +68,16 @@ const uuidGen = Cc["@mozilla.org/uuid-ge
  * The {@link element.Store} provides a mapping between web element
  * references and DOM elements for each browsing context.  It also provides
  * functionality for looking up and retrieving elements.
  *
  * @namespace
  */
 this.element = {};
 
-element.Key = "element-6066-11e4-a52e-4f735466cecf";
-element.LegacyKey = "ELEMENT";
-
 element.Strategy = {
   ClassName: "class name",
   Selector: "css selector",
   ID: "id",
   Name: "name",
   LinkText: "link text",
   PartialLinkText: "partial link text",
   TagName: "tag name",
@@ -125,102 +122,128 @@ element.Store = class {
   addAll(els) {
     let add = this.add.bind(this);
     return [...els].map(add);
   }
 
   /**
    * Make an element seen.
    *
-   * @param {Element} el
+   * @param {(Element|WindowProxy|XULElement)} el
    *    Element to add to set of seen elements.
    *
-   * @return {string}
+   * @return {WebElement}
    *     Web element reference associated with element.
+   *
+   * @throws {TypeError}
+   *     If <var>el</var> is not an {@link Element} or a {@link XULElement}.
    */
   add(el) {
+    const isDOMElement = element.isDOMElement(el);
+    const isSVGElement = element.isSVGElement(el);
+    const isDOMWindow = element.isDOMWindow(el);
+    const isXULElement = element.isXULElement(el);
+    const context = isXULElement ? "chrome" : "content";
+
+    if (!(isDOMElement || isSVGElement || isDOMWindow || isXULElement)) {
+      throw new TypeError("Expected Element, SVGElement, " +
+          pprint`WindowProxy, or XULElement, got: ${el}`);
+    }
+
     for (let i in this.els) {
       let foundEl;
       try {
         foundEl = this.els[i].get();
       } catch (e) {}
 
       if (foundEl) {
         if (new XPCNativeWrapper(foundEl) == new XPCNativeWrapper(el)) {
-          return i;
+          return WebElement.fromUUID(i, context);
         }
 
       // cleanup reference to gc'd element
       } else {
         delete this.els[i];
       }
     }
 
-    let id = element.generateUUID();
-    this.els[id] = Cu.getWeakReference(el);
-    return id;
+    let webEl = WebElement.from(el);
+    this.els[webEl.uuid] = Cu.getWeakReference(el);
+    return webEl;
   }
 
   /**
    * Determine if the provided web element reference has been seen
    * before/is in the element store.
    *
    * Unlike when getting the element, a staleness check is not
    * performed.
    *
-   * @param {string} uuid
+   * @param {WebElement} webEl
    *     Element's associated web element reference.
    *
    * @return {boolean}
    *     True if element is in the store, false otherwise.
+   *
+   * @throws {TypeError}
+   *     If <var>webEl</var> is not a {@link WebElement}.
    */
-  has(uuid) {
-    return Object.keys(this.els).includes(uuid);
+  has(webEl) {
+    if (!(webEl instanceof WebElement)) {
+      throw new TypeError(
+          pprint`Expected web element, got: ${webEl}`);
+    }
+    return Object.keys(this.els).includes(webEl.uuid);
   }
 
   /**
-   * Retrieve a DOM element by its unique web element reference/UUID.
+   * Retrieve a DOM {@link Element} or a {@link XULElement} by its
+   * unique {@link WebElement} reference.
    *
-   * Upon retrieving the element, an element staleness check is
-   * performed.
-   *
-   * @param {string} uuid
-   *     Web element reference, or UUID.
+   * @param {WebElement} webEl
+   *     Web element reference to find the associated {@link Element}
+   *     of.
    * @param {WindowProxy} window
    *     Current browsing context, which may differ from the associate
    *     browsing context of <var>el</var>.
    *
-   * @returns {Element}
+   * @returns {(Element|XULElement)}
    *     Element associated with reference.
    *
+   * @throws {TypeError}
+   *     If <var>webEl</var> is not a {@link WebElement}.
    * @throws {NoSuchElementError}
    *     If the web element reference <var>uuid</var> has not been
    *     seen before.
    * @throws {StaleElementReferenceError}
    *     If the element has gone stale, indicating it is no longer
    *     attached to the DOM, or its node document is no longer the
    *     active document.
    */
-  get(uuid, window) {
-    if (!this.has(uuid)) {
+  get(webEl, window) {
+    if (!(webEl instanceof WebElement)) {
+      throw new TypeError(
+          pprint`Expected web element, got: ${webEl}`);
+    }
+    if (!this.has(webEl)) {
       throw new NoSuchElementError(
-          "Web element reference not seen before: " + uuid);
+          "Web element reference not seen before: " + webEl.uuid);
     }
 
     let el;
-    let ref = this.els[uuid];
+    let ref = this.els[webEl.uuid];
     try {
       el = ref.get();
     } catch (e) {
-      delete this.els[uuid];
+      delete this.els[webEl.uuid];
     }
 
     if (element.isStale(el, window)) {
       throw new StaleElementReferenceError(
-          pprint`The element reference of ${el || uuid} stale; ` +
+          pprint`The element reference of ${el || webEl.uuid} is stale; ` +
               "either the element is no longer attached to the DOM, " +
               "it is not in the current frame context, " +
               "or the document has been refreshed");
     }
 
     return el;
   }
 };
@@ -658,21 +681,16 @@ element.isCollection = function(seq) {
 
 element.makeWebElement = function(uuid) {
   return {
     [element.Key]: uuid,
     [element.LegacyKey]: uuid,
   };
 };
 
-element.generateUUID = function() {
-  let uuid = uuidGen.generateUUID().toString();
-  return uuid.substring(1, uuid.length - 1);
-};
-
 /**
  * Determines if <var>el</var> is stale.
  *
  * A stale element is an element no longer attached to the DOM or which
  * node document is not the active document of the current browsing
  * context.
  *
  * The currently selected browsing context, specified through