diff --git a/core/api/src/main/java/org/onosproject/net/host/HostProviderService.java b/core/api/src/main/java/org/onosproject/net/host/HostProviderService.java
index dfb0ac2..9125049 100644
--- a/core/api/src/main/java/org/onosproject/net/host/HostProviderService.java
+++ b/core/api/src/main/java/org/onosproject/net/host/HostProviderService.java
@@ -17,6 +17,7 @@
 
 import org.onlab.packet.IpAddress;
 import org.onosproject.net.HostId;
+import org.onosproject.net.HostLocation;
 import org.onosproject.net.provider.ProviderService;
 
 /**
@@ -49,4 +50,11 @@
      */
     void removeIpFromHost(HostId hostId, IpAddress ipAddress);
 
+    /**
+     * Notifies the core when a location is no longer associated with a host.
+     *
+     * @param hostId id of the host
+     * @param location location of host that vanished
+     */
+    void removeLocationFromHost(HostId hostId, HostLocation location);
 }
diff --git a/core/api/src/main/java/org/onosproject/net/host/HostStore.java b/core/api/src/main/java/org/onosproject/net/host/HostStore.java
index e73fbb7..e8a3e56 100644
--- a/core/api/src/main/java/org/onosproject/net/host/HostStore.java
+++ b/core/api/src/main/java/org/onosproject/net/host/HostStore.java
@@ -22,6 +22,7 @@
 import org.onosproject.net.DeviceId;
 import org.onosproject.net.Host;
 import org.onosproject.net.HostId;
+import org.onosproject.net.HostLocation;
 import org.onosproject.net.provider.ProviderId;
 import org.onosproject.store.Store;
 
@@ -64,6 +65,14 @@
     HostEvent removeIp(HostId hostId, IpAddress ipAddress);
 
     /**
+     * Removes the specified location from the host entry.
+     *
+     * @param hostId host identification
+     * @param location location to be removed
+     */
+    void removeLocation(HostId hostId, HostLocation location);
+
+    /**
      * Returns the number of hosts in the store.
      *
      * @return host count
diff --git a/core/common/src/test/java/org/onosproject/store/trivial/SimpleHostStore.java b/core/common/src/test/java/org/onosproject/store/trivial/SimpleHostStore.java
index 98a9252..89214e4 100644
--- a/core/common/src/test/java/org/onosproject/store/trivial/SimpleHostStore.java
+++ b/core/common/src/test/java/org/onosproject/store/trivial/SimpleHostStore.java
@@ -167,10 +167,16 @@
 
     @Override
     public HostEvent removeIp(HostId hostId, IpAddress ipAddress) {
+        // TODO implement this
         return null;
     }
 
     @Override
+    public void removeLocation(HostId hostId, HostLocation location) {
+        hosts.get(hostId).locations().remove(location);
+    }
+
+    @Override
     public int getHostCount() {
         return hosts.size();
     }
diff --git a/core/net/src/main/java/org/onosproject/net/host/impl/HostManager.java b/core/net/src/main/java/org/onosproject/net/host/impl/HostManager.java
index 06f3120..ee0fc4c 100644
--- a/core/net/src/main/java/org/onosproject/net/host/impl/HostManager.java
+++ b/core/net/src/main/java/org/onosproject/net/host/impl/HostManager.java
@@ -30,16 +30,18 @@
 import org.onlab.util.Tools;
 import org.onosproject.cfg.ComponentConfigService;
 import org.onosproject.incubator.net.intf.InterfaceService;
-import org.onosproject.net.ConnectPoint;
-import org.onosproject.net.DeviceId;
-import org.onosproject.net.Host;
-import org.onosproject.net.HostId;
+import org.onosproject.net.HostLocation;
+import org.onosproject.net.edge.EdgePortService;
+import org.onosproject.net.provider.AbstractListenerProviderRegistry;
 import org.onosproject.net.config.NetworkConfigEvent;
 import org.onosproject.net.config.NetworkConfigListener;
 import org.onosproject.net.config.NetworkConfigService;
 import org.onosproject.net.config.basics.BasicHostConfig;
+import org.onosproject.net.ConnectPoint;
+import org.onosproject.net.DeviceId;
+import org.onosproject.net.Host;
+import org.onosproject.net.HostId;
 import org.onosproject.net.device.DeviceService;
-import org.onosproject.net.edge.EdgePortService;
 import org.onosproject.net.host.HostAdminService;
 import org.onosproject.net.host.HostDescription;
 import org.onosproject.net.host.HostEvent;
@@ -51,7 +53,6 @@
 import org.onosproject.net.host.HostStore;
 import org.onosproject.net.host.HostStoreDelegate;
 import org.onosproject.net.packet.PacketService;
-import org.onosproject.net.provider.AbstractListenerProviderRegistry;
 import org.onosproject.net.provider.AbstractProviderService;
 import org.osgi.service.component.ComponentContext;
 import org.slf4j.Logger;
@@ -413,8 +414,8 @@
             checkValidity();
             Host host = store.getHost(hostId);
 
-            // Disallow removing inexistent host or host provided by others
-            if (host == null || !host.providerId().equals(provider().id())) {
+            if (!allowedToChange(hostId)) {
+                log.info("Request to remove {} is ignored due to provider mismatch", hostId);
                 return;
             }
 
@@ -430,8 +431,35 @@
         public void removeIpFromHost(HostId hostId, IpAddress ipAddress) {
             checkNotNull(hostId, HOST_ID_NULL);
             checkValidity();
+
+            if (!allowedToChange(hostId)) {
+                log.info("Request to remove {} from {} is ignored due to provider mismatch",
+                        ipAddress, hostId);
+                return;
+            }
+
             store.removeIp(hostId, ipAddress);
         }
+
+        @Override
+        public void removeLocationFromHost(HostId hostId, HostLocation location) {
+            checkNotNull(hostId, HOST_ID_NULL);
+            checkValidity();
+
+            if (!allowedToChange(hostId)) {
+                log.info("Request to remove {} from {} is ignored due to provider mismatch",
+                        location, hostId);
+                return;
+            }
+
+            store.removeLocation(hostId, location);
+        }
+
+        private boolean allowedToChange(HostId hostId) {
+            // Disallow removing inexistent host or host provided by others
+            Host host = store.getHost(hostId);
+            return host != null && host.providerId().equals(provider().id());
+        }
     }
 
     // Store delegate to re-post events emitted from the store.
diff --git a/core/store/dist/src/main/java/org/onosproject/store/host/impl/DistributedHostStore.java b/core/store/dist/src/main/java/org/onosproject/store/host/impl/DistributedHostStore.java
index 64d24a7..76d14e7 100644
--- a/core/store/dist/src/main/java/org/onosproject/store/host/impl/DistributedHostStore.java
+++ b/core/store/dist/src/main/java/org/onosproject/store/host/impl/DistributedHostStore.java
@@ -266,6 +266,29 @@
     }
 
     @Override
+    public void removeLocation(HostId hostId, HostLocation location) {
+        hosts.compute(hostId, (id, existingHost) -> {
+            if (existingHost != null) {
+                checkState(Objects.equals(hostId.mac(), existingHost.mac()),
+                        "Existing and new MAC addresses differ.");
+                checkState(Objects.equals(hostId.vlanId(), existingHost.vlan()),
+                        "Existing and new VLANs differ.");
+
+                Set<HostLocation> locations = new HashSet<>(existingHost.locations());
+                locations.remove(location);
+
+                // Remove entire host if we are removing the last location
+                return locations.isEmpty() ? null :
+                        new DefaultHost(existingHost.providerId(),
+                                hostId, existingHost.mac(), existingHost.vlan(),
+                                locations, existingHost.ipAddresses(),
+                                existingHost.configured(), existingHost.annotations());
+            }
+            return null;
+        });
+    }
+
+    @Override
     public int getHostCount() {
         return hosts.size();
     }