diff --git a/metropolis/node/BUILD.bazel b/metropolis/node/BUILD.bazel
index d043c1c..2a7d296 100644
--- a/metropolis/node/BUILD.bazel
+++ b/metropolis/node/BUILD.bazel
@@ -21,6 +21,7 @@
     deps = [
         "//metropolis/proto/common",
         "@com_github_vishvananda_netlink//:netlink",
+        "@io_k8s_apimachinery//pkg/util/validation",
     ],
 )
 
@@ -145,4 +146,5 @@
     name = "node_test",
     srcs = ["labels_test.go"],
     embed = [":node"],
+    deps = ["@io_k8s_apimachinery//pkg/util/validation"],
 )
diff --git a/metropolis/node/core/cluster/cluster_bootstrap.go b/metropolis/node/core/cluster/cluster_bootstrap.go
index 820dffc..bb82df9 100644
--- a/metropolis/node/core/cluster/cluster_bootstrap.go
+++ b/metropolis/node/core/cluster/cluster_bootstrap.go
@@ -142,11 +142,11 @@
 			l.Pairs = l.Pairs[:common.MaxLabelsPerNode]
 		}
 		for _, pair := range l.Pairs {
-			if err := common.ValidateLabel(pair.Key); err != nil {
+			if err := common.ValidateLabelKey(pair.Key); err != nil {
 				supervisor.Logger(ctx).Warningf("Skipping label %q/%q: key invalid: %v", pair.Key, pair.Value, err)
 				continue
 			}
-			if err := common.ValidateLabel(pair.Value); err != nil {
+			if err := common.ValidateLabelValue(pair.Value); err != nil {
 				supervisor.Logger(ctx).Warningf("Skipping label %q/%q: value invalid: %v", pair.Key, pair.Value, err)
 				continue
 			}
diff --git a/metropolis/node/core/curator/impl_leader_curator.go b/metropolis/node/core/curator/impl_leader_curator.go
index cf88b37..d4e8d1a 100644
--- a/metropolis/node/core/curator/impl_leader_curator.go
+++ b/metropolis/node/core/curator/impl_leader_curator.go
@@ -378,11 +378,11 @@
 			k := pair.Key
 			v := pair.Value
 
-			if err := common.ValidateLabel(k); err != nil {
+			if err := common.ValidateLabelKey(k); err != nil {
 				rpc.Trace(ctx).Printf("Label key %q is invalid: %v, skipping", k, err)
 				continue
 			}
-			if err := common.ValidateLabel(v); err != nil {
+			if err := common.ValidateLabelValue(v); err != nil {
 				rpc.Trace(ctx).Printf("Label value %q (key %q) is invalid: %v, skipping", v, k, err)
 				continue
 			}
diff --git a/metropolis/node/core/curator/impl_leader_management.go b/metropolis/node/core/curator/impl_leader_management.go
index 4321fbe..585cb94 100644
--- a/metropolis/node/core/curator/impl_leader_management.go
+++ b/metropolis/node/core/curator/impl_leader_management.go
@@ -496,10 +496,10 @@
 	for _, pair := range req.Upsert {
 		k := pair.Key
 		v := pair.Value
-		if err := common.ValidateLabel(k); err != nil {
+		if err := common.ValidateLabelKey(k); err != nil {
 			return nil, status.Errorf(codes.InvalidArgument, "invalid upsert key %q: %v", k, err)
 		}
-		if err := common.ValidateLabel(v); err != nil {
+		if err := common.ValidateLabelValue(v); err != nil {
 			return nil, status.Errorf(codes.InvalidArgument, "invalid upsert value %q (key %q): %v", v, k, err)
 		}
 		if _, ok := keysToUpsert[k]; ok {
@@ -508,7 +508,7 @@
 		keysToUpsert[k] = v
 	}
 	for _, k := range req.Delete {
-		if err := common.ValidateLabel(k); err != nil {
+		if err := common.ValidateLabelKey(k); err != nil {
 			return nil, status.Errorf(codes.InvalidArgument, "invalid delete key %q: %v", k, err)
 		}
 		if _, ok := keysToUpsert[k]; ok {
diff --git a/metropolis/node/core/curator/state_node.go b/metropolis/node/core/curator/state_node.go
index 52af3df..93d2a8d 100644
--- a/metropolis/node/core/curator/state_node.go
+++ b/metropolis/node/core/curator/state_node.go
@@ -397,10 +397,10 @@
 		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 {
+			if err := common.ValidateLabelKey(pair.Key); err != nil {
 				continue
 			}
-			if err := common.ValidateLabel(pair.Value); err != nil {
+			if err := common.ValidateLabelValue(pair.Value); err != nil {
 				continue
 			}
 			n.labels[pair.Key] = pair.Value
diff --git a/metropolis/node/labels.go b/metropolis/node/labels.go
index f26e5bd..93f1551 100644
--- a/metropolis/node/labels.go
+++ b/metropolis/node/labels.go
@@ -3,6 +3,9 @@
 import (
 	"fmt"
 	"regexp"
+	"strings"
+
+	"k8s.io/apimachinery/pkg/util/validation"
 
 	cpb "source.monogon.dev/metropolis/proto/common"
 )
@@ -26,6 +29,8 @@
 	// ErrLabelInvalidCharacter is returned by ValidateLabel if the label key/value
 	// contains an invalid character.
 	ErrLabelInvalidCharacter = fmt.Errorf("invalid character")
+	ErrLabelEmptyPrefix      = fmt.Errorf("empty prefix")
+	ErrLabelInvalidPrefix    = fmt.Errorf("invalid prefix")
 )
 
 const (
@@ -34,20 +39,46 @@
 	MaxLabelsPerNode = 128
 )
 
-// ValidateLabel ensures that a given node label key/value component is valid:
+func validatePrefix(prefix string) error {
+	if prefix == "" {
+		return ErrLabelEmptyPrefix
+	}
+	if errs := validation.IsDNS1123Subdomain(prefix); len(errs) > 0 {
+		return ErrLabelInvalidPrefix
+	}
+	return nil
+}
+
+// ValidateLabelKey ensures that a given node label key 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.
+//  5. Optional slash-delimited prefix which contains a valid 'DNS subdomain'.
 //
 // If it's valid, nil is returned. Otherwise, one of ErrLabelEmpty,
 // ErrLabelTooLong, ErrLabelInvalidFirstCharacter or ErrLabelInvalidCharacter is
 // returned.
-func ValidateLabel(v string) error {
+func ValidateLabelKey(v string) error {
+	// Split away prefix.
+	parts := strings.Split(v, "/")
+	switch len(parts) {
+	case 1:
+	case 2:
+		prefix := parts[0]
+		if err := validatePrefix(prefix); err != nil {
+			return err
+		}
+		v = parts[1]
+	default:
+		return ErrLabelInvalidPrefix
+	}
+
 	if len(v) == 0 {
 		return ErrLabelEmpty
 	}
+
 	if len(v) > 63 {
 		return ErrLabelTooLong
 	}
@@ -65,6 +96,37 @@
 	return nil
 }
 
+// ValidateLabelValue ensures that a given node label value is valid:
+//
+//  1. 0 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 ErrLabelTooLong,
+// ErrLabelInvalidFirstCharacter, or ErrLabelInvalidLastCharacter,
+// ErrLabelInvalidCharacter is returned.
+func ValidateLabelValue(v string) error {
+	if len(v) == 0 {
+		return nil
+	}
+	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 character, and we've already
+	// checked that so we can check the entire string here.
+	if !reLabelBody.MatchString(v) {
+		return ErrLabelInvalidCharacter
+	}
+	return nil
+}
+
 // GetNodeLabel retrieves a node label by key, returning its value or an empty
 // string if no labels with this key is set on the node.
 func GetNodeLabel(labels *cpb.NodeLabels, key string) string {
diff --git a/metropolis/node/labels_test.go b/metropolis/node/labels_test.go
index 0e8b799..c8e1a86 100644
--- a/metropolis/node/labels_test.go
+++ b/metropolis/node/labels_test.go
@@ -3,9 +3,38 @@
 import (
 	"errors"
 	"testing"
+
+	"k8s.io/apimachinery/pkg/util/validation"
 )
 
-func TestValidateLabelKeyValue(t *testing.T) {
+func TestValidateLabelKey(t *testing.T) {
+	for i, te := range []struct {
+		in   string
+		want error
+	}{
+		{"foo", nil},
+		{"example.com/", ErrLabelEmpty},
+		{"foo-bar.baz_barfoo", nil},
+		{"-", ErrLabelInvalidFirstCharacter},
+		{"-invalid", ErrLabelInvalidFirstCharacter},
+		{"invalid-", ErrLabelInvalidLastCharacter},
+		{"", ErrLabelEmpty},
+		{"accordingtoallknownlawsofaviationthereisnowaythatabeeshouldbeabletofly", ErrLabelTooLong},
+		{"example.com/annotation", nil},
+		{"/annotation", ErrLabelEmptyPrefix},
+		{"_internal.example.com/annotation", ErrLabelInvalidPrefix},
+		{"./annotation", ErrLabelInvalidPrefix},
+		{"../annotation", ErrLabelInvalidPrefix},
+		{"tcp:80.example.com/annotation", ErrLabelInvalidPrefix},
+		{"github.com/monogon-dev/monogon/annotation", ErrLabelInvalidPrefix},
+	} {
+		if got := ValidateLabelKey(te.in); !errors.Is(got, te.want) {
+			t.Errorf("%d (%q): wanted %v, got %v", i, te.in, te.want, got)
+		}
+	}
+}
+
+func TestValidateLabelValue(t *testing.T) {
 	for i, te := range []struct {
 		in   string
 		want error
@@ -15,12 +44,23 @@
 		{"-", ErrLabelInvalidFirstCharacter},
 		{"-invalid", ErrLabelInvalidFirstCharacter},
 		{"invalid-", ErrLabelInvalidLastCharacter},
-		{"", ErrLabelEmpty},
+		{"", nil},
 		{"accordingtoallknownlawsofaviationthereisnowaythatabeeshouldbeabletofly", ErrLabelTooLong},
 		{"example.com/annotation", ErrLabelInvalidCharacter},
+		{"/annotation", ErrLabelInvalidFirstCharacter},
+		{"_internal.example.com/annotation", ErrLabelInvalidFirstCharacter},
+		{"./annotation", ErrLabelInvalidFirstCharacter},
+		{"../annotation", ErrLabelInvalidFirstCharacter},
+		{"tcp:80.example.com/annotation", ErrLabelInvalidCharacter},
+		{"github.com/monogon-dev/monogon/annotation", ErrLabelInvalidCharacter},
 	} {
-		if got := ValidateLabel(te.in); !errors.Is(got, te.want) {
-			t.Errorf("%d: wanted %v, got %v", i, te.want, got)
+		// Test our implementation against test cases.
+		if got := ValidateLabelValue(te.in); !errors.Is(got, te.want) {
+			t.Errorf("%d (%q): wanted %v, got %v", i, te.in, te.want, got)
+		}
+		// Validate test cases against Kubernetes.
+		if errs := validation.IsValidLabelValue(te.in); (te.want == nil) != (len(errs) == 0) {
+			t.Errorf("%d (%q): wanted %v, kubernetes implementation returned %v", i, te.in, te.want, errs)
 		}
 	}
 }