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 {