diff --git a/src/android/net/ip/IpClient.java b/src/android/net/ip/IpClient.java
index 00aa599..b08e0b9 100644
--- a/src/android/net/ip/IpClient.java
+++ b/src/android/net/ip/IpClient.java
@@ -95,6 +95,7 @@
 import android.util.SparseArray;
 
 import androidx.annotation.NonNull;
+import androidx.annotation.Nullable;
 
 import com.android.internal.annotations.VisibleForTesting;
 import com.android.internal.util.HexDump;
@@ -740,9 +741,27 @@
         mLinkObserver = new IpClientLinkObserver(
                 mContext, getHandler(),
                 mInterfaceName,
-                (ifaceUp) -> sendMessage(EVENT_NETLINK_LINKPROPERTIES_CHANGED, ifaceUp
-                        ? ARG_LINKPROP_CHANGED_LINKSTATE_UP
-                        : ARG_LINKPROP_CHANGED_LINKSTATE_DOWN),
+                new IpClientLinkObserver.Callback() {
+                    @Override
+                    public void update(boolean linkState) {
+                        sendMessage(EVENT_NETLINK_LINKPROPERTIES_CHANGED, linkState
+                                ? ARG_LINKPROP_CHANGED_LINKSTATE_UP
+                                : ARG_LINKPROP_CHANGED_LINKSTATE_DOWN);
+                    }
+
+                    @Override
+                    public void onIpv6AddressRemoved(final Inet6Address targetIp) {
+                        // The update of Gratuitous NA target addresses set should be only accessed
+                        // from the handler thread of IpClient StateMachine, keeping the behaviour
+                        // consistent with relying on the non-blocking NetworkObserver callbacks,
+                        // see {@link registerObserverForNonblockingCallback}. This can be done
+                        // by either sending a message to StateMachine or posting a handler.
+                        getHandler().post(() -> {
+                            if (!mGratuitousNaTargetAddresses.contains(targetIp)) return;
+                            updateGratuitousNaTargetSet(targetIp, false /* remove address */);
+                        });
+                    }
+                },
                 config, mLog, mDependencies) {
             @Override
             public void onInterfaceAdded(String iface) {
@@ -775,21 +794,6 @@
                 logMsg(msg);
             }
 
-            @Override
-            public void onInterfaceAddressRemoved(LinkAddress address, String iface) {
-                super.onInterfaceAddressRemoved(address, iface);
-                if (!mInterfaceName.equals(iface)) return;
-                if (!address.isIpv6()) return;
-                final Inet6Address targetIp = (Inet6Address) address.getAddress();
-                if (mGratuitousNaTargetAddresses.contains(targetIp)) {
-                    mGratuitousNaTargetAddresses.remove(targetIp);
-
-                    final String msg = "Global IPv6 address: " + targetIp
-                            + " has removed from the set of gratuitous NA target address.";
-                    logMsg(msg);
-                }
-            }
-
             private void logMsg(String msg) {
                 Log.d(mTag, msg);
                 getHandler().post(() -> mLog.log("OBSERVED " + msg));
@@ -1663,6 +1667,7 @@
         transmitPacket(packet, sockAddress, "Failed to send GARP");
     }
 
+    @Nullable
     private static Inet6Address getIpv6LinkLocalAddress(final LinkProperties newLp) {
         for (LinkAddress la : newLp.getLinkAddresses()) {
             if (!la.isIpv6()) continue;
@@ -1672,6 +1677,16 @@
         return null;
     }
 
+    private void updateGratuitousNaTargetSet(@NonNull final Inet6Address targetIp, boolean add) {
+        if (add) {
+            mGratuitousNaTargetAddresses.add(targetIp);
+        } else {
+            mGratuitousNaTargetAddresses.remove(targetIp);
+        }
+        mLog.log((add ? "Add" : "Remove") + " global IPv6 address " + targetIp
+                + (add ? " to" : " from") + " the set of gratuitous NA target address.");
+    }
+
     private void maybeSendGratuitousNAs(final LinkProperties lp, boolean afterRoaming) {
         if (!lp.hasGlobalIpv6Address()) return;
 
@@ -1692,7 +1707,7 @@
                         + targetIp.getHostAddress() + (afterRoaming ? " after roaming" : ""));
             }
             sendGratuitousNA(srcIp, targetIp);
-            if (!afterRoaming) mGratuitousNaTargetAddresses.add(targetIp);
+            if (!afterRoaming) updateGratuitousNaTargetSet(targetIp, true /* add address */);
         }
     }
 
diff --git a/src/android/net/ip/IpClientLinkObserver.java b/src/android/net/ip/IpClientLinkObserver.java
index f8ba367..adc527b 100644
--- a/src/android/net/ip/IpClientLinkObserver.java
+++ b/src/android/net/ip/IpClientLinkObserver.java
@@ -42,6 +42,8 @@
 import android.system.OsConstants;
 import android.util.Log;
 
+import androidx.annotation.NonNull;
+
 import com.android.net.module.util.netlink.NduseroptMessage;
 import com.android.net.module.util.netlink.NetlinkConstants;
 import com.android.net.module.util.netlink.NetlinkMessage;
@@ -56,6 +58,7 @@
 import com.android.networkstack.apishim.common.NetworkInformationShim;
 import com.android.server.NetworkObserver;
 
+import java.net.Inet6Address;
 import java.net.InetAddress;
 import java.util.ArrayList;
 import java.util.Arrays;
@@ -111,6 +114,13 @@
          *                  with {@link #getLinkProperties()} in particular.
          */
         void update(boolean linkState);
+
+        /**
+         * Called when an IPv6 address was removed from the interface.
+         *
+         * @param addr The removed IPv6 address.
+         */
+        void onIpv6AddressRemoved(Inet6Address addr);
     }
 
     /** Configuration parameters for IpClientLinkObserver. */
@@ -262,7 +272,7 @@
         }
     }
 
-    private void updateInterfaceAddress(final LinkAddress address, boolean add) {
+    private void updateInterfaceAddress(@NonNull final LinkAddress address, boolean add) {
         final boolean changed;
         final boolean linkState;
         synchronized (this) {
@@ -275,6 +285,10 @@
         }
         if (changed) {
             mCallback.update(linkState);
+            if (!add && address.isIpv6()) {
+                final Inet6Address addr = (Inet6Address) address.getAddress();
+                mCallback.onIpv6AddressRemoved(addr);
+            }
         }
     }