diff --git a/services/core/java/com/android/server/connectivity/Nat464Xlat.java b/services/core/java/com/android/server/connectivity/Nat464Xlat.java
index 741cb5b..e6b2d26 100644
--- a/services/core/java/com/android/server/connectivity/Nat464Xlat.java
+++ b/services/core/java/com/android/server/connectivity/Nat464Xlat.java
@@ -81,6 +81,9 @@
         RUNNING,      // start() called, and the stacked iface is known to be up.
     }
 
+    /** NAT64 prefix currently in use. Only valid in STARTING or RUNNING states. */
+    private IpPrefix mNat64PrefixInUse;
+    /** NAT64 prefix (if any) discovered from DNS via RFC 7050. */
     private IpPrefix mNat64PrefixFromDns;
     private String mBaseIface;
     private String mIface;
@@ -178,9 +181,10 @@
             return;
         }
 
+        mNat64PrefixInUse = getNat64Prefix();
         String addrStr = null;
         try {
-            addrStr = mNetd.clatdStart(baseIface, getNat64Prefix().toString());
+            addrStr = mNetd.clatdStart(baseIface, mNat64PrefixInUse.toString());
         } catch (RemoteException | ServiceSpecificException e) {
             Slog.e(TAG, "Error starting clatd on " + baseIface + ": " + e);
         }
@@ -211,12 +215,13 @@
         } catch (RemoteException | IllegalStateException e) {
             Slog.e(TAG, "Error unregistering clatd observer on " + mBaseIface + ": " + e);
         }
+        mNat64PrefixInUse = null;
         mIface = null;
         mBaseIface = null;
         if (requiresClat(mNetwork)) {
             mState = State.DISCOVERING;
         } else {
-            stopPrefixDiscovery();
+            stopPrefixDiscovery();  // Enters IDLE state.
         }
     }
 
@@ -274,19 +279,32 @@
     private void startPrefixDiscovery() {
         try {
             mDnsResolver.startPrefix64Discovery(getNetId());
-            mState = State.DISCOVERING;
         } catch (RemoteException | ServiceSpecificException e) {
             Slog.e(TAG, "Error starting prefix discovery on netId " + getNetId() + ": " + e);
         }
+        mState = State.DISCOVERING;
     }
 
     private void stopPrefixDiscovery() {
         try {
             mDnsResolver.stopPrefix64Discovery(getNetId());
-            mState = State.IDLE;
         } catch (RemoteException | ServiceSpecificException e) {
             Slog.e(TAG, "Error stopping prefix discovery on netId " + getNetId() + ": " + e);
         }
+        mState = State.IDLE;
+    }
+
+    private void maybeHandleNat64PrefixChange() {
+        final IpPrefix newPrefix = getNat64Prefix();
+        if (!Objects.equals(mNat64PrefixInUse, newPrefix)) {
+            Slog.d(TAG, "NAT64 prefix changed from " + mNat64PrefixInUse + " to "
+                    + newPrefix);
+            stop();
+            // It's safe to call update here, even though this method is called from update, because
+            // stop() is guaranteed to have moved out of STARTING and RUNNING, which are the only
+            // states in which this method can be called.
+            update();
+        }
     }
 
     /**
@@ -325,11 +343,11 @@
                 // Stop clatd and go back into DISCOVERING or idle.
                 if (!shouldStartClat(mNetwork)) {
                     stop();
+                    break;
                 }
+                // Only necessary while clat is actually started.
+                maybeHandleNat64PrefixChange();
                 break;
-                // TODO: support the NAT64 prefix changing after it's been discovered. There is
-                // no need to support this at the moment because it cannot happen without
-                // changes to the Dns64Configuration code in netd.
         }
     }
 
@@ -347,6 +365,8 @@
      * has no idea that 464xlat is running on top of it.
      */
     public void fixupLinkProperties(@NonNull LinkProperties oldLp, @NonNull LinkProperties lp) {
+        // This must be done even if clatd is not running, because otherwise shouldStartClat would
+        // never return true.
         lp.setNat64Prefix(getNat64Prefix());
 
         if (!isRunning()) {
diff --git a/tests/net/java/com/android/server/ConnectivityServiceTest.java b/tests/net/java/com/android/server/ConnectivityServiceTest.java
index b864e37..dad0363 100644
--- a/tests/net/java/com/android/server/ConnectivityServiceTest.java
+++ b/tests/net/java/com/android/server/ConnectivityServiceTest.java
@@ -5969,6 +5969,9 @@
         final LinkAddress myIpv6 = new LinkAddress("2001:db8:1::1/64");
         final String kNat64PrefixString = "2001:db8:64:64:64:64::";
         final IpPrefix kNat64Prefix = new IpPrefix(InetAddress.getByName(kNat64PrefixString), 96);
+        final String kOtherNat64PrefixString = "64:ff9b::";
+        final IpPrefix kOtherNat64Prefix = new IpPrefix(
+                InetAddress.getByName(kOtherNat64PrefixString), 96);
         final RouteInfo defaultRoute = new RouteInfo((IpPrefix) null, myIpv6.getAddress(),
                                                      MOBILE_IFNAME);
         final RouteInfo ipv6Subnet = new RouteInfo(myIpv6, null, MOBILE_IFNAME);
@@ -6082,6 +6085,24 @@
         }
         reset(mMockNetd);
 
+        // Change the NAT64 prefix without first removing it.
+        // Expect clatd to be stopped and started with the new prefix.
+        mService.mNetdEventCallback.onNat64PrefixEvent(cellNetId, true /* added */,
+                kOtherNat64PrefixString, 96);
+        networkCallback.expectLinkPropertiesThat(mCellNetworkAgent,
+                (lp) -> lp.getStackedLinks().size() == 0);
+        verify(mMockNetd, times(1)).clatdStop(MOBILE_IFNAME);
+        assertRoutesRemoved(cellNetId, stackedDefault);
+
+        verify(mMockNetd, times(1)).clatdStart(MOBILE_IFNAME, kOtherNat64Prefix.toString());
+        networkCallback.expectLinkPropertiesThat(mCellNetworkAgent,
+                (lp) -> lp.getNat64Prefix().equals(kOtherNat64Prefix));
+        clat.interfaceLinkStateChanged(CLAT_PREFIX + MOBILE_IFNAME, true);
+        networkCallback.expectLinkPropertiesThat(mCellNetworkAgent,
+                (lp) -> lp.getStackedLinks().size() == 1);
+        assertRoutesAdded(cellNetId, stackedDefault);
+        reset(mMockNetd);
+
         // Add ipv4 address, expect that clatd and prefix discovery are stopped and stacked
         // linkproperties are cleaned up.
         cellLp.addLinkAddress(myIpv4);
@@ -6096,7 +6117,7 @@
         networkCallback.expectCallback(CallbackEntry.LINK_PROPERTIES_CHANGED, mCellNetworkAgent);
         LinkProperties actualLpAfterIpv4 = mCm.getLinkProperties(mCellNetworkAgent.getNetwork());
         LinkProperties expected = new LinkProperties(cellLp);
-        expected.setNat64Prefix(kNat64Prefix);
+        expected.setNat64Prefix(kOtherNat64Prefix);
         assertEquals(expected, actualLpAfterIpv4);
         assertEquals(0, actualLpAfterIpv4.getStackedLinks().size());
         assertRoutesRemoved(cellNetId, stackedDefault);
@@ -6115,7 +6136,7 @@
 
         // Stopping prefix discovery causes netd to tell us that the NAT64 prefix is gone.
         mService.mNetdEventCallback.onNat64PrefixEvent(cellNetId, false /* added */,
-                kNat64PrefixString, 96);
+                kOtherNat64PrefixString, 96);
         networkCallback.expectLinkPropertiesThat(mCellNetworkAgent,
                 (lp) -> lp.getNat64Prefix() == null);