diff --git a/metropolis/proto/api/management.proto b/metropolis/proto/api/management.proto
index bd7bd5b..421898a 100644
--- a/metropolis/proto/api/management.proto
+++ b/metropolis/proto/api/management.proto
@@ -109,6 +109,14 @@
             need: PERMISSION_DELETE_NODE
         };
     }
+
+    // Add, update or remove labels from a given node. The given node must exist,
+    // but can be in any state.
+    rpc UpdateNodeLabels(UpdateNodeLabelsRequest) returns (UpdateNodeLabelsResponse) {
+        option (metropolis.proto.ext.authorization) = {
+            need: PERMISSION_UPDATE_NODE_LABELS
+        };
+    }
 }
 
 message GetRegisterTicketRequest {
@@ -197,6 +205,9 @@
     // node has actually passed high assurance hardware attestation against the
     // cluster.
     metropolis.proto.common.NodeTPMUsage tpm_usage = 8;
+
+    // Labels attached to the node.
+    metropolis.proto.common.NodeLabels labels = 9;
 }
 
 message ApproveNodeRequest {
@@ -416,4 +427,35 @@
   ActivationMode activation_mode = 3;
 }
 
-message UpdateNodeResponse {}
\ No newline at end of file
+message UpdateNodeResponse {}
+
+message UpdateNodeLabelsRequest {
+  // node uniquely identifies the node subject to this request.
+  oneof node {
+    // pubkey is the Ed25519 public key of this node, which can be used to
+    // generate the node's ID.
+    bytes pubkey = 1;
+    // id is the human-readable identifier of the node, based on its public
+    // key.
+    string id = 2;
+  }
+
+  message Pair {
+    string key = 1;
+    string value = 2;
+  }
+  // Labels to be added (created or updated by key).
+  //
+  // The given pairs must have unique, valid keys and valid values.
+  repeated Pair upsert = 3;
+
+  // Labels to be removed (by key).
+  //
+  // The given keys do not have to exist on the node, but cannot intersect with
+  // keys given in the upsert list.
+  repeated string delete = 4;
+}
+
+message UpdateNodeLabelsResponse {
+}
+
diff --git a/metropolis/proto/common/common.proto b/metropolis/proto/common/common.proto
index b870d20..a0e8c73 100644
--- a/metropolis/proto/common/common.proto
+++ b/metropolis/proto/common/common.proto
@@ -64,6 +64,34 @@
     KubernetesController kubernetes_controller = 3;
 }
 
+// NodeLabels are labels assigned to a node.
+//
+// Labels are string key/value pairs modeled after the Kubernetes label concept.
+// They can be used to assign user-specific metadata to nodes like IDs from other
+// systems or geographical location. They are treated like opaque strings by
+// Metropolis itself.
+//
+// Every key and value must be a string between 1 and 63 characters long
+// (inclusive). Each character must be a valid ASCII character from the following
+// range: a-z, A-Z, 0-9 '-', '_' or '.'. The first character must be a-z, A-Z or
+// 0-9. This is close but not exact to DNS label requirements (for example, '.'
+// or '_' are generally not valid DNS label parts... but that's a discussion for
+// another day).
+//
+// Keys must not repeat across node labels - that is, NodeLabels must be
+// convertable to/from a string/string map in Go. Pair ordering is not preserved,
+// but pair order in labels received from Metropolis API calls is stable (however
+// it is arbitrary).
+//
+// A node cannot have more than 128 labels.
+message NodeLabels {
+    message Pair {
+        string key = 1;
+        string value = 2;
+    }
+    repeated Pair pairs = 1;
+}
+
 // NodeState is the state of a Metropolis node from the point of view of the
 // cluster it is a part of (or intending to be a part of).
 enum NodeState {
diff --git a/metropolis/proto/ext/authorization.proto b/metropolis/proto/ext/authorization.proto
index 1a0e759..4c27f3e 100644
--- a/metropolis/proto/ext/authorization.proto
+++ b/metropolis/proto/ext/authorization.proto
@@ -28,6 +28,7 @@
     PERMISSION_UPDATE_NODE = 7;
     PERMISSION_DECOMMISSION_NODE = 8;
     PERMISSION_DELETE_NODE = 9;
+    PERMISSION_UPDATE_NODE_LABELS = 10;
 }
 
 // Authorization policy for an RPC method. This message/API does not have the