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());
+    }
+}
+
diff --git a/nearby/tests/src/com/android/server/nearby/common/bluetooth/fastpair/FastPairHistoryItemTest.java b/nearby/tests/src/com/android/server/nearby/common/bluetooth/fastpair/FastPairHistoryItemTest.java
new file mode 100644
index 0000000..81651bc
--- /dev/null
+++ b/nearby/tests/src/com/android/server/nearby/common/bluetooth/fastpair/FastPairHistoryItemTest.java
@@ -0,0 +1,71 @@
+/*
+ * Copyright (C) 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.io.BaseEncoding.base16;
+import static com.google.common.primitives.Bytes.concat;
+import static com.google.common.truth.Truth.assertThat;
+
+import android.platform.test.annotations.Presubmit;
+
+import androidx.test.filters.SmallTest;
+import androidx.test.runner.AndroidJUnit4;
+
+import com.google.common.hash.Hashing;
+import com.google.protobuf.ByteString;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+/**
+ * Unit tests for {@link FastPairHistoryItem}.
+ */
+@Presubmit
+@SmallTest
+@RunWith(AndroidJUnit4.class)
+public class FastPairHistoryItemTest {
+
+    @Test
+    public void inputMatchedPublicAddress_isMatchedReturnTrue() {
+        final byte[] accountKey = base16().decode("0123456789ABCDEF");
+        final byte[] publicAddress = BluetoothAddress.decode("11:22:33:44:55:66");
+        final byte[] hashValue =
+                Hashing.sha256().hashBytes(concat(accountKey, publicAddress)).asBytes();
+
+        FastPairHistoryItem historyItem =
+                FastPairHistoryItem
+                        .create(ByteString.copyFrom(accountKey), ByteString.copyFrom(hashValue));
+
+        assertThat(historyItem.isMatched(publicAddress)).isTrue();
+    }
+
+    @Test
+    public void inputNotMatchedPublicAddress_isMatchedReturnFalse() {
+        final byte[] accountKey = base16().decode("0123456789ABCDEF");
+        final byte[] publicAddress1 = BluetoothAddress.decode("11:22:33:44:55:66");
+        final byte[] publicAddress2 = BluetoothAddress.decode("11:22:33:44:55:77");
+        final byte[] hashValue =
+                Hashing.sha256().hashBytes(concat(accountKey, publicAddress1)).asBytes();
+
+        FastPairHistoryItem historyItem =
+                FastPairHistoryItem
+                        .create(ByteString.copyFrom(accountKey), ByteString.copyFrom(hashValue));
+
+        assertThat(historyItem.isMatched(publicAddress2)).isFalse();
+    }
+}
+