diff --git a/metropolis/node/BUILD.bazel b/metropolis/node/BUILD.bazel
index 609bcd4..876dbfc 100644
--- a/metropolis/node/BUILD.bazel
+++ b/metropolis/node/BUILD.bazel
@@ -1,4 +1,4 @@
-load("@io_bazel_rules_go//go:def.bzl", "go_library")
+load("@io_bazel_rules_go//go:def.bzl", "go_library", "go_test")
 load("//metropolis/node/build:def.bzl", "erofs_image", "verity_image")
 load("//metropolis/node/build:efi.bzl", "efi_unified_kernel_image")
 load("//metropolis/node/build/mkimage:def.bzl", "node_image")
@@ -8,6 +8,7 @@
     name = "node",
     srcs = [
         "ids.go",
+        "labels.go",
         "net_ips.go",
         "net_protocols.go",
         "ports.go",
@@ -139,3 +140,9 @@
     os_name = "Metropolis Node",
     stamp_var = "STABLE_MONOGON_metropolis_version",
 )
+
+go_test(
+    name = "node_test",
+    srcs = ["labels_test.go"],
+    embed = [":node"],
+)
diff --git a/metropolis/node/core/curator/impl_leader_curator.go b/metropolis/node/core/curator/impl_leader_curator.go
index 259677b..b88525f 100644
--- a/metropolis/node/core/curator/impl_leader_curator.go
+++ b/metropolis/node/core/curator/impl_leader_curator.go
@@ -200,6 +200,7 @@
 		Status:     np.Status,
 		Clusternet: np.Clusternet,
 		State:      np.FsmState,
+		Labels:     np.Labels,
 	})
 }
 
diff --git a/metropolis/node/core/curator/impl_leader_management.go b/metropolis/node/core/curator/impl_leader_management.go
index ff18f72..c0bab97 100644
--- a/metropolis/node/core/curator/impl_leader_management.go
+++ b/metropolis/node/core/curator/impl_leader_management.go
@@ -12,6 +12,7 @@
 	"google.golang.org/grpc/status"
 	dpb "google.golang.org/protobuf/types/known/durationpb"
 
+	common "source.monogon.dev/metropolis/node"
 	"source.monogon.dev/metropolis/node/core/consensus"
 	"source.monogon.dev/metropolis/node/core/identity"
 	"source.monogon.dev/metropolis/node/core/rpc"
@@ -232,7 +233,17 @@
 			TimeSinceHeartbeat: dpb.New(lhb),
 			Health:             health,
 			TpmUsage:           node.tpmUsage,
+			Labels:             &cpb.NodeLabels{},
 		}
+		for k, v := range node.labels {
+			entry.Labels.Pairs = append(entry.Labels.Pairs, &cpb.NodeLabels_Pair{
+				Key:   k,
+				Value: v,
+			})
+		}
+		sort.Slice(entry.Labels.Pairs, func(i, j int) bool {
+			return entry.Labels.Pairs[i].Key < entry.Labels.Pairs[j].Key
+		})
 
 		// Evaluate the filter expression for this node. Send the node, if it's
 		// kept by the filter.
@@ -460,3 +471,83 @@
 	err = nodeDestroy(ctx, l.leadership, node)
 	return &apb.DeleteNodeResponse{}, err
 }
+
+func (l *leaderManagement) UpdateNodeLabels(ctx context.Context, req *apb.UpdateNodeLabelsRequest) (*apb.UpdateNodeLabelsResponse, error) {
+	// Get node ID from request.
+	var id string
+	switch rid := req.Node.(type) {
+	case *apb.UpdateNodeLabelsRequest_Pubkey:
+		if len(rid.Pubkey) != ed25519.PublicKeySize {
+			return nil, status.Errorf(codes.InvalidArgument, "pubkey must be %d bytes long", ed25519.PublicKeySize)
+		}
+		// Convert the pubkey into node ID.
+		id = identity.NodeID(rid.Pubkey)
+	case *apb.UpdateNodeLabelsRequest_Id:
+		id = rid.Id
+	default:
+		return nil, status.Errorf(codes.InvalidArgument, "exactly one of pubkey or id must be set")
+	}
+
+	keysToUpsert := make(map[string]string)
+	keysToDelete := make(map[string]bool)
+
+	for _, pair := range req.Upsert {
+		k := pair.Key
+		v := pair.Value
+		if err := common.ValidateLabel(k); err != nil {
+			return nil, status.Errorf(codes.InvalidArgument, "invalid upsert key %q: %v", k, err)
+		}
+		if err := common.ValidateLabel(v); err != nil {
+			return nil, status.Errorf(codes.InvalidArgument, "invalid upsert value %q (key %q): %v", v, k, err)
+		}
+		if _, ok := keysToUpsert[k]; ok {
+			return nil, status.Errorf(codes.InvalidArgument, "repeated upsert key %q", k)
+		}
+		keysToUpsert[k] = v
+	}
+	for _, k := range req.Delete {
+		if err := common.ValidateLabel(k); err != nil {
+			return nil, status.Errorf(codes.InvalidArgument, "invalid delete key %q: %v", k, err)
+		}
+		if _, ok := keysToUpsert[k]; ok {
+			return nil, status.Errorf(codes.InvalidArgument, "delete key %q conflicts with upsert key", k)
+		}
+		if _, ok := keysToDelete[k]; ok {
+			return nil, status.Errorf(codes.InvalidArgument, "repeated delete key %q", k)
+		}
+		keysToDelete[k] = true
+	}
+
+	// Take l.muNodes before modifying the node.
+	l.muNodes.Lock()
+	defer l.muNodes.Unlock()
+
+	// Load the node matching the request.
+	node, err := nodeLoad(ctx, l.leadership, id)
+	if errors.Is(err, errNodeNotFound) {
+		return nil, status.Errorf(codes.NotFound, "node %s not found", id)
+	}
+	if err != nil {
+		return nil, status.Errorf(codes.InvalidArgument, "while loading node %s: %v", id, err)
+	}
+
+	// Apply changes.
+	for k, v := range keysToUpsert {
+		node.labels[k] = v
+	}
+	for k := range keysToDelete {
+		delete(node.labels, k)
+	}
+
+	// Check we don't end up with too many labels.
+	if nlabels := len(node.labels); nlabels > common.MaxLabelsPerNode {
+		return nil, status.Errorf(codes.OutOfRange, "change would result in too many labels on node (%d, limit %d)", nlabels, common.MaxLabelsPerNode)
+	}
+
+	// Save changes.
+	if err := nodeSave(ctx, l.leadership, node); err != nil {
+		return nil, err
+	}
+
+	return &apb.UpdateNodeLabelsResponse{}, nil
+}
diff --git a/metropolis/node/core/curator/impl_leader_test.go b/metropolis/node/core/curator/impl_leader_test.go
index 29f1f58..d3c3de1 100644
--- a/metropolis/node/core/curator/impl_leader_test.go
+++ b/metropolis/node/core/curator/impl_leader_test.go
@@ -61,6 +61,9 @@
 		if optI.icc != nil {
 			opt.icc = optI.icc
 		}
+		if optI.labels != nil {
+			opt.labels = optI.labels
+		}
 	}
 
 	// Start a single-node etcd cluster.
@@ -109,6 +112,10 @@
 	// Here we would enable the leader node's roles. But for tests, we don't enable
 	// any.
 
+	if opt.labels != nil {
+		cNode.labels = opt.labels
+	}
+
 	cc := DefaultClusterConfiguration()
 	if opt.icc != nil {
 		cc, err = ClusterConfigurationFromInitial(opt.icc)
@@ -248,7 +255,8 @@
 type fakeLeaderOption struct {
 	// icc is the initial cluster configuration to be set when bootstrapping the
 	//fake cluster. If not set, uses system defaults.
-	icc *cpb.ClusterConfiguration
+	icc    *cpb.ClusterConfiguration
+	labels map[string]string
 }
 
 // fakeLeaderData is returned by fakeLeader and contains information about the
@@ -1762,3 +1770,108 @@
 		})
 	}
 }
+
+func TestNodeLabels(t *testing.T) {
+	ctx, ctxC := context.WithCancel(context.Background())
+	defer ctxC()
+
+	cl := fakeLeader(t, &fakeLeaderOption{
+		labels: map[string]string{
+			"test1": "a",
+			"test2": "b",
+			"test3": "c",
+		},
+	})
+	checkLabels := func(t *testing.T, n *apb.Node, labels map[string]string) {
+		t.Helper()
+		if n.Labels == nil || len(n.Labels.Pairs) != len(labels) {
+			t.Fatalf("Expected %d label pair(s), got: %+v", len(labels), n.Labels)
+		}
+		got := make(map[string]string)
+		for _, pair := range n.Labels.Pairs {
+			got[pair.Key] = pair.Value
+		}
+		errors := false
+		for k, v := range labels {
+			if got[k] != v {
+				t.Errorf("Wanted label %q with value %q, got %q", k, v, got[k])
+				errors = true
+			}
+		}
+		for k, v := range got {
+			if labels[k] == "" {
+				t.Errorf("Unexpected label %q with value %q", k, v)
+				errors = true
+			}
+		}
+		if errors {
+			t.Fatalf("Label differences found")
+		}
+	}
+
+	// Expect preconfigured labels to be set.
+	mgmt := apb.NewManagementClient(cl.mgmtConn)
+	nodes := getNodes(t, ctx, mgmt, "")
+	if len(nodes) != 1 {
+		t.Fatalf("Expected 1 node, got %d", len(nodes))
+	}
+	checkLabels(t, nodes[0], map[string]string{"test1": "a", "test2": "b", "test3": "c"})
+
+	// Expect label mutation to work.
+	_, err := mgmt.UpdateNodeLabels(ctx, &apb.UpdateNodeLabelsRequest{
+		Node: &apb.UpdateNodeLabelsRequest_Id{
+			Id: nodes[0].Id,
+		},
+		Upsert: []*apb.UpdateNodeLabelsRequest_Pair{
+			{Key: "test2", Value: "d"},
+		},
+		Delete: []string{"test1"},
+	})
+	if err != nil {
+		t.Fatalf("UpdateNodeLabels: %v", err)
+	}
+	nodes = getNodes(t, ctx, mgmt, "")
+	if len(nodes) != 1 {
+		t.Fatalf("Expected 1 node, got %d", len(nodes))
+	}
+	checkLabels(t, nodes[0], map[string]string{"test2": "d", "test3": "c"})
+
+	// Test some invalid mutations, make sure they error out and don't change the
+	// label state.
+	for i, te := range []*apb.UpdateNodeLabelsRequest{
+		// Invalid because of repeat upsert key.
+		{
+			Upsert: []*apb.UpdateNodeLabelsRequest_Pair{
+				{Key: "repeat", Value: "a"},
+				{Key: "repeat", Value: "b"},
+			},
+			Delete: []string{},
+		},
+		// Invalid because of repeat delete key.
+		{
+			Upsert: []*apb.UpdateNodeLabelsRequest_Pair{},
+			Delete: []string{"test3", "test3"},
+		},
+		// Invalid because of key contained both in upsert and delete.
+		{
+			Upsert: []*apb.UpdateNodeLabelsRequest_Pair{
+				{Key: "test3", Value: "e"},
+			},
+			Delete: []string{"test3"},
+		},
+	} {
+		t.Run(fmt.Sprintf("bad%d", i), func(t *testing.T) {
+			te.Node = &apb.UpdateNodeLabelsRequest_Id{Id: nodes[0].Id}
+			_, err := mgmt.UpdateNodeLabels(ctx, te)
+			if err == nil {
+				t.Errorf("Should have errored out")
+			}
+			// Make sure that the state didn't get mutated, even if an error occurred.
+			nodes = getNodes(t, ctx, mgmt, "")
+			if len(nodes) != 1 {
+				t.Fatalf("Expected 1 node, got %d", len(nodes))
+			}
+			checkLabels(t, nodes[0], map[string]string{"test2": "d", "test3": "c"})
+		})
+	}
+}
diff --git a/metropolis/node/core/curator/proto/api/api.proto b/metropolis/node/core/curator/proto/api/api.proto
index ff30ff1..ef7e24c 100644
--- a/metropolis/node/core/curator/proto/api/api.proto
+++ b/metropolis/node/core/curator/proto/api/api.proto
@@ -176,6 +176,7 @@
     metropolis.proto.common.NodeClusterNetworking clusternet = 4;
     // The node's 'lifecycle' state from the point of view of the cluster.
     metropolis.proto.common.NodeState state = 5;
+    metropolis.proto.common.NodeLabels labels = 6;
 };
 
 // WatchRequest specifies what data the caller is interested in. This influences
diff --git a/metropolis/node/core/curator/proto/private/storage.proto b/metropolis/node/core/curator/proto/private/storage.proto
index 23b60ac..681bb0a 100644
--- a/metropolis/node/core/curator/proto/private/storage.proto
+++ b/metropolis/node/core/curator/proto/private/storage.proto
@@ -40,6 +40,8 @@
     // tpm_usage describes whether this node has a TPM 2.0 and whether it's using
     // it.
     metropolis.proto.common.NodeTPMUsage tpm_usage = 8;
+
+    metropolis.proto.common.NodeLabels labels = 9;
 }
 
 // Information about the cluster owner, currently the only Metropolis management
diff --git a/metropolis/node/core/curator/state_node.go b/metropolis/node/core/curator/state_node.go
index a0d9dc3..18ea200 100644
--- a/metropolis/node/core/curator/state_node.go
+++ b/metropolis/node/core/curator/state_node.go
@@ -22,17 +22,20 @@
 	"encoding/hex"
 	"fmt"
 	"net/netip"
+	"sort"
 
 	clientv3 "go.etcd.io/etcd/client/v3"
 	"google.golang.org/grpc/codes"
 	"google.golang.org/grpc/status"
 	"google.golang.org/protobuf/proto"
 
+	common "source.monogon.dev/metropolis/node"
 	"source.monogon.dev/metropolis/node/core/consensus"
-	ppb "source.monogon.dev/metropolis/node/core/curator/proto/private"
 	"source.monogon.dev/metropolis/node/core/identity"
 	"source.monogon.dev/metropolis/node/core/rpc"
 	"source.monogon.dev/metropolis/pkg/pki"
+
+	ppb "source.monogon.dev/metropolis/node/core/curator/proto/private"
 	cpb "source.monogon.dev/metropolis/proto/common"
 )
 
@@ -99,6 +102,8 @@
 	// wireguard peer, but only the pod network will have a single large route
 	// installed into the host routing table.
 	networkPrefixes []netip.Prefix
+
+	labels map[string]string
 }
 
 // NewNodeForBootstrap creates a brand new node without regard for any other
@@ -247,6 +252,7 @@
 		Roles:            &cpb.NodeRoles{},
 		Status:           n.status,
 		TpmUsage:         n.tpmUsage,
+		Labels:           &cpb.NodeLabels{},
 	}
 	if n.kubernetesWorker != nil {
 		msg.Roles.KubernetesWorker = &cpb.NodeRoles_KubernetesWorker{}
@@ -281,6 +287,15 @@
 			Prefixes:        prefixes,
 		}
 	}
+	for k, v := range n.labels {
+		msg.Labels.Pairs = append(msg.Labels.Pairs, &cpb.NodeLabels_Pair{
+			Key:   k,
+			Value: v,
+		})
+	}
+	sort.Slice(msg.Labels.Pairs, func(i, j int) bool {
+		return msg.Labels.Pairs[i].Key < msg.Labels.Pairs[j].Key
+	})
 	return msg
 }
 
@@ -296,6 +311,7 @@
 		state:            msg.FsmState,
 		status:           msg.Status,
 		tpmUsage:         msg.TpmUsage,
+		labels:           make(map[string]string),
 	}
 	if msg.Roles.KubernetesWorker != nil {
 		n.kubernetesWorker = &NodeRoleKubernetesWorker{}
@@ -348,6 +364,19 @@
 			n.networkPrefixes = append(n.networkPrefixes, nip)
 		}
 	}
+	if l := msg.Labels; l != nil {
+		for _, pair := range l.Pairs {
+			// Skip invalid keys/values that were somehow persisted into etcd. They will be
+			// removed on next marshal/save.
+			if err := common.ValidateLabel(pair.Key); err != nil {
+				continue
+			}
+			if err := common.ValidateLabel(pair.Value); err != nil {
+				continue
+			}
+			n.labels[pair.Key] = pair.Value
+		}
+	}
 	return n, nil
 }
 
diff --git a/metropolis/node/labels.go b/metropolis/node/labels.go
new file mode 100644
index 0000000..08d0c6e
--- /dev/null
+++ b/metropolis/node/labels.go
@@ -0,0 +1,64 @@
+package node
+
+import (
+	"fmt"
+	"regexp"
+)
+
+var (
+	reLabelFirstLast = regexp.MustCompile(`^[a-zA-Z0-9]$`)
+	reLabelBody      = regexp.MustCompile(`^[a-zA-Z0-9\-._]*$`)
+
+	// ErrLabelEmpty is returned by ValidateLabel if the label key/value is not at
+	// least one character long.
+	ErrLabelEmpty = fmt.Errorf("empty")
+	// ErrLabelTooLong is returned by ValidateLabel if the label key/value is more
+	// than 63 characters long.
+	ErrLabelTooLong = fmt.Errorf("too long")
+	// ErrLabelInvalidFirstCharacter is returned by ValidateLabel if the label
+	// key/value contains an invalid character on the first position.
+	ErrLabelInvalidFirstCharacter = fmt.Errorf("first character not a letter or number")
+	// ErrLabelInvalidLastCharacter is returned by ValidateLabel if the label
+	// key/value contains an invalid character on the last position.
+	ErrLabelInvalidLastCharacter = fmt.Errorf("last character not a letter or number")
+	// ErrLabelInvalidCharacter is returned by ValidateLabel if the label key/value
+	// contains an invalid character.
+	ErrLabelInvalidCharacter = fmt.Errorf("invalid character")
+)
+
+const (
+	// MaxLabelsPerNode is the absolute maximum of labels that can be attached to a
+	// node.
+	MaxLabelsPerNode = 128
+)
+
+// ValidateLabel ensures that a given node label key/value component is valid:
+//
+//  1. 1 to 63 characters long (inclusive);
+//  2. Characters are all ASCII a-z A-Z 0-9 '_', '-' or '.';
+//  3. The first character is ASCII a-z A-Z or 0-9.
+//  4. The last character is ASCII a-z A-Z or 0-9.
+//
+// If it's valid, nil is returned. Otherwise, one of ErrLabelEmpty,
+// ErrLabelTooLong, ErrLabelInvalidFirstCharacter or ErrLabelInvalidCharacter is
+// returned.
+func ValidateLabel(v string) error {
+	if len(v) == 0 {
+		return ErrLabelEmpty
+	}
+	if len(v) > 63 {
+		return ErrLabelTooLong
+	}
+	if !reLabelFirstLast.MatchString(string(v[0])) {
+		return ErrLabelInvalidFirstCharacter
+	}
+	if !reLabelFirstLast.MatchString(string(v[len(v)-1])) {
+		return ErrLabelInvalidLastCharacter
+	}
+	// Body characters are a superset of the first/last characters, and we've already
+	// checked those so we can check the entire string here.
+	if !reLabelBody.MatchString(v) {
+		return ErrLabelInvalidCharacter
+	}
+	return nil
+}
diff --git a/metropolis/node/labels_test.go b/metropolis/node/labels_test.go
new file mode 100644
index 0000000..0e8b799
--- /dev/null
+++ b/metropolis/node/labels_test.go
@@ -0,0 +1,26 @@
+package node
+
+import (
+	"errors"
+	"testing"
+)
+
+func TestValidateLabelKeyValue(t *testing.T) {
+	for i, te := range []struct {
+		in   string
+		want error
+	}{
+		{"foo", nil},
+		{"foo-bar.baz_barfoo", nil},
+		{"-", ErrLabelInvalidFirstCharacter},
+		{"-invalid", ErrLabelInvalidFirstCharacter},
+		{"invalid-", ErrLabelInvalidLastCharacter},
+		{"", ErrLabelEmpty},
+		{"accordingtoallknownlawsofaviationthereisnowaythatabeeshouldbeabletofly", ErrLabelTooLong},
+		{"example.com/annotation", ErrLabelInvalidCharacter},
+	} {
+		if got := ValidateLabel(te.in); !errors.Is(got, te.want) {
+			t.Errorf("%d: wanted %v, got %v", i, te.want, got)
+		}
+	}
+}