diff --git a/nearby/service/Android.bp b/nearby/service/Android.bp
index 14a96d1..f1f7c44 100644
--- a/nearby/service/Android.bp
+++ b/nearby/service/Android.bp
@@ -43,6 +43,7 @@
         "androidx.core_core",
         "auto_value_annotations",
         "guava",
+        "libprotobuf-java-lite",
     ],
     sdk_version: "system_server_current",
     plugins: ["auto_value_plugin"],
diff --git a/nearby/service/java/com/android/server/nearby/common/bluetooth/fastpair/FastPairHistoryItem.java b/nearby/service/java/com/android/server/nearby/common/bluetooth/fastpair/FastPairHistoryItem.java
new file mode 100644
index 0000000..d2816dc
--- /dev/null
+++ b/nearby/service/java/com/android/server/nearby/common/bluetooth/fastpair/FastPairHistoryItem.java
@@ -0,0 +1,60 @@
+/*
+ * Copyright 2021 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.nearby.common.bluetooth.fastpair;
+
+import static com.google.common.primitives.Bytes.concat;
+
+import com.google.auto.value.AutoValue;
+import com.google.common.hash.Hashing;
+import com.google.protobuf.ByteString;
+
+import java.util.Arrays;
+
+/**
+ * It contains the sha256 of "account key + headset's public address" to identify the headset which
+ * has paired with the account. Previously, account key is the only information for Fast Pair to
+ * identify the headset, but Fast Pair can't identify the headset in initial pairing, there is no
+ * account key data advertising from headset.
+ */
+@AutoValue
+public abstract class FastPairHistoryItem {
+
+    /** Creates an instance of {@link FastPairHistoryItem}.
+     *
+     * @param accountKey key of an account that has paired with the headset.
+     * @param sha256AccountKeyPublicAddress hash value of account key and headset's public address.
+     */
+    public static FastPairHistoryItem create(
+            ByteString accountKey, ByteString sha256AccountKeyPublicAddress) {
+        return new AutoValue_FastPairHistoryItem(accountKey, sha256AccountKeyPublicAddress);
+    }
+
+    abstract ByteString accountKey();
+
+    abstract ByteString sha256AccountKeyPublicAddress();
+
+    // Return true if the input public address is considered the same as this history item. Because
+    // of privacy concern, Fast Pair does not really store the public address, it is identified by
+    // the SHA256 of the account key and the public key.
+    final boolean isMatched(byte[] publicAddress) {
+        return Arrays.equals(
+            sha256AccountKeyPublicAddress().toByteArray(),
+            Hashing.sha256().hashBytes(concat(accountKey().toByteArray(), publicAddress))
+                .asBytes());
+    }
+}
+