diff --git a/adb/adb_mdns.h b/adb/adb_mdns.h
index cc22581..6b37355 100644
--- a/adb/adb_mdns.h
+++ b/adb/adb_mdns.h
@@ -27,12 +27,62 @@
 const int kADBSecurePairingServiceRefIndex = 1;
 const int kADBSecureConnectServiceRefIndex = 2;
 
+// Each ADB Secure service advertises with a TXT record indicating the version
+// using a key/value pair per RFC 6763 (https://tools.ietf.org/html/rfc6763).
+//
+// The first key/value pair is always the version of the protocol.
+// There may be more key/value pairs added after.
+//
+// The version is purposely represented as the single letter "v" due to the
+// need to minimize DNS traffic. The version starts at 1.  With each breaking
+// protocol change, the version is incremented by 1.
+//
+// Newer adb clients/daemons need to recognize and either reject
+// or be backward-compatible with older verseions if there is a mismatch.
+//
+// Relevant sections:
+//
+// """
+// 6.4.  Rules for Keys in DNS-SD Key/Value Pairs
+//
+// The key MUST be at least one character.  DNS-SD TXT record strings
+// beginning with an '=' character (i.e., the key is missing) MUST be
+// silently ignored.
+//
+// ...
+//
+// 6.5.  Rules for Values in DNS-SD Key/Value Pairs
+//
+// If there is an '=' in a DNS-SD TXT record string, then everything
+// after the first '=' to the end of the string is the value.  The value
+// can contain any eight-bit values including '='.
+// """
+
+#define ADB_SECURE_SERVICE_VERSION_TXT_RECORD(ver) ("v=" #ver)
+
+// Client/service versions are initially defined to be matching,
+// but may go out of sync as different clients and services
+// try to talk to each other.
+#define ADB_SECURE_SERVICE_VERSION 1
+#define ADB_SECURE_CLIENT_VERSION ADB_SECURE_SERVICE_VERSION
+
+const char* kADBSecurePairingServiceTxtRecord =
+        ADB_SECURE_SERVICE_VERSION_TXT_RECORD(ADB_SECURE_SERVICE_VERSION);
+const char* kADBSecureConnectServiceTxtRecord =
+        ADB_SECURE_SERVICE_VERSION_TXT_RECORD(ADB_SECURE_SERVICE_VERSION);
+
 const char* kADBDNSServices[] = {
         kADBServiceType,
         kADBSecurePairingServiceType,
         kADBSecureConnectServiceType,
 };
 
+const char* kADBDNSServiceTxtRecords[] = {
+        nullptr,
+        kADBSecurePairingServiceTxtRecord,
+        kADBSecureConnectServiceTxtRecord,
+};
+
 const int kNumADBDNSServices = arraysize(kADBDNSServices);
 
 #endif
diff --git a/adb/client/transport_mdns.cpp b/adb/client/transport_mdns.cpp
index 0f88f78..f5811a4 100644
--- a/adb/client/transport_mdns.cpp
+++ b/adb/client/transport_mdns.cpp
@@ -111,13 +111,14 @@
     virtual ~ResolvedService() = default;
 
     ResolvedService(std::string serviceName, std::string regType, uint32_t interfaceIndex,
-                    const char* hosttarget, uint16_t port)
+                    const char* hosttarget, uint16_t port, int version)
         : serviceName_(serviceName),
           regType_(regType),
           hosttarget_(hosttarget),
           port_(port),
           sa_family_(0),
-          ip_addr_data_(NULL) {
+          ip_addr_data_(NULL),
+          serviceVersion_(version) {
         memset(ip_addr_, 0, sizeof(ip_addr_));
 
         /* TODO: We should be able to get IPv6 support by adding
@@ -137,6 +138,8 @@
         } else {
             Initialize();
         }
+
+        D("Client version: %d Service version: %d\n", clientVersion_, serviceVersion_);
     }
 
     void Connect(const sockaddr* address) {
@@ -204,6 +207,7 @@
                                adb_secure_foreach_service_callback cb);
 
   private:
+    int clientVersion_ = ADB_SECURE_CLIENT_VERSION;
     std::string serviceName_;
     std::string regType_;
     std::string hosttarget_;
@@ -211,6 +215,7 @@
     int sa_family_;
     const void* ip_addr_data_;
     char ip_addr_[INET6_ADDRSTRLEN];
+    int serviceVersion_;
 };
 
 // static
@@ -327,16 +332,55 @@
     std::string regType_;
 };
 
-static void DNSSD_API register_resolved_mdns_service(DNSServiceRef sdRef,
-                                                     DNSServiceFlags flags,
-                                                     uint32_t interfaceIndex,
-                                                     DNSServiceErrorType errorCode,
-                                                     const char* fullname,
-                                                     const char* hosttarget,
-                                                     uint16_t port,
-                                                     uint16_t /*txtLen*/,
-                                                     const unsigned char* /*txtRecord*/,
-                                                     void* context) {
+// Returns the version the device wanted to advertise,
+// or -1 if parsing fails.
+static int parse_version_from_txt_record(uint16_t txtLen, const unsigned char* txtRecord) {
+    if (!txtLen) return -1;
+    if (!txtRecord) return -1;
+
+    // https://tools.ietf.org/html/rfc6763
+    // """
+    // 6.1.  General Format Rules for DNS TXT Records
+    //
+    // A DNS TXT record can be up to 65535 (0xFFFF) bytes long.  The total
+    // length is indicated by the length given in the resource record header
+    // in the DNS message.  There is no way to tell directly from the data
+    // alone how long it is (e.g., there is no length count at the start, or
+    // terminating NULL byte at the end).
+    // """
+
+    // Let's trust the TXT record's length byte
+    // Worst case, it wastes 255 bytes
+    std::vector<char> recordAsString(txtLen + 1, '\0');
+    char* str = recordAsString.data();
+
+    memcpy(str, txtRecord + 1 /* skip the length byte */, txtLen);
+
+    // Check if it's the version key
+    static const char* versionKey = "v=";
+    size_t versionKeyLen = strlen(versionKey);
+
+    if (strncmp(versionKey, str, versionKeyLen)) return -1;
+
+    auto valueStart = str + versionKeyLen;
+
+    long parsedNumber = strtol(valueStart, 0, 10);
+
+    // No valid conversion. Also, 0
+    // is not a valid version.
+    if (!parsedNumber) return -1;
+
+    // Outside bounds of long.
+    if (parsedNumber == LONG_MIN || parsedNumber == LONG_MAX) return -1;
+
+    // Possibly valid version
+    return static_cast<int>(parsedNumber);
+}
+
+static void DNSSD_API register_resolved_mdns_service(
+        DNSServiceRef sdRef, DNSServiceFlags flags, uint32_t interfaceIndex,
+        DNSServiceErrorType errorCode, const char* fullname, const char* hosttarget, uint16_t port,
+        uint16_t txtLen, const unsigned char* txtRecord, void* context) {
     D("Resolved a service.");
     std::unique_ptr<DiscoveredService> discovered(
         reinterpret_cast<DiscoveredService*>(context));
@@ -346,8 +390,14 @@
         return;
     }
 
+    // TODO: Reject certain combinations of invalid or mismatched client and
+    // service versions here before creating anything.
+    // At the moment, there is nothing to reject, so accept everything
+    // as an optimistic default.
+    auto serviceVersion = parse_version_from_txt_record(txtLen, txtRecord);
+
     auto resolved = new ResolvedService(discovered->ServiceName(), discovered->RegType(),
-                                        interfaceIndex, hosttarget, ntohs(port));
+                                        interfaceIndex, hosttarget, ntohs(port), serviceVersion);
 
     if (! resolved->Initialized()) {
         delete resolved;
diff --git a/adb/daemon/mdns.cpp b/adb/daemon/mdns.cpp
index 35e3d90..fa98340 100644
--- a/adb/daemon/mdns.cpp
+++ b/adb/daemon/mdns.cpp
@@ -67,9 +67,37 @@
     std::string hostname = "adb-";
     hostname += android::base::GetProperty("ro.serialno", "unidentified");
 
-    auto error = DNSServiceRegister(&mdns_refs[index], 0, 0, hostname.c_str(),
-                                    kADBDNSServices[index], nullptr, nullptr,
-                                    htobe16((uint16_t)port), 0, nullptr, mdns_callback, nullptr);
+    // https://tools.ietf.org/html/rfc6763
+    // """
+    // The format of the data within a DNS TXT record is one or more
+    // strings, packed together in memory without any intervening gaps or
+    // padding bytes for word alignment.
+    //
+    // The format of each constituent string within the DNS TXT record is a
+    // single length byte, followed by 0-255 bytes of text data.
+    // """
+    //
+    // Therefore:
+    // 1. Begin with the string length
+    // 2. No null termination
+
+    std::vector<char> txtRecord;
+
+    if (kADBDNSServiceTxtRecords[index]) {
+        size_t txtRecordStringLength = strlen(kADBDNSServiceTxtRecords[index]);
+
+        txtRecord.resize(1 +                    // length byte
+                         txtRecordStringLength  // string bytes
+        );
+
+        txtRecord[0] = (char)txtRecordStringLength;
+        memcpy(txtRecord.data() + 1, kADBDNSServiceTxtRecords[index], txtRecordStringLength);
+    }
+
+    auto error = DNSServiceRegister(
+            &mdns_refs[index], 0, 0, hostname.c_str(), kADBDNSServices[index], nullptr, nullptr,
+            htobe16((uint16_t)port), (uint16_t)txtRecord.size(),
+            txtRecord.empty() ? nullptr : txtRecord.data(), mdns_callback, nullptr);
 
     if (error != kDNSServiceErr_NoError) {
         LOG(ERROR) << "Could not register mDNS service " << kADBDNSServices[index] << ", error ("