diff --git a/src/empathy-map-view.c b/src/empathy-map-view.c
index 287d9b6..30c123b 100644
--- a/src/empathy-map-view.c
+++ b/src/empathy-map-view.c
@@ -56,6 +56,9 @@ typedef struct {
   ChamplainView *map_view;
   ChamplainLayer *layer;
   guint timeout_id;
+  /* reffed (EmpathyContact *) => borrowed (ChamplainMarker *) */
+  GHashTable *markers;
+  gulong members_changed_id;
 } EmpathyMapView;
 
 static void
@@ -72,22 +75,49 @@ map_view_state_changed (ChamplainView *view,
     ephy_spinner_stop (EPHY_SPINNER (window->throbber));
 }
 
+static gboolean
+contact_has_location (EmpathyContact *contact)
+{
+  GHashTable *location;
+
+  location = empathy_contact_get_location (contact);
+
+  if (location == NULL || g_hash_table_size (location) == 0)
+    return FALSE;
+
+  return TRUE;
+}
+
+static ChamplainMarker * create_marker (EmpathyMapView *window,
+    EmpathyContact *contact);
+
 static void
-map_view_marker_update_position (ChamplainMarker *marker,
+map_view_update_contact_position (EmpathyMapView *self,
     EmpathyContact *contact)
 {
   gdouble lon, lat;
   GValue *value;
   GHashTable *location;
+  ChamplainMarker *marker;
+  gboolean has_location;
 
-  location = empathy_contact_get_location (contact);
+  has_location = contact_has_location (contact);
 
-  if (location == NULL ||
-      g_hash_table_size (location) == 0)
-  {
-    champlain_base_marker_animate_out (CHAMPLAIN_BASE_MARKER (marker));
-    return;
-  }
+  marker = g_hash_table_lookup (self->markers, contact);
+  if (marker == NULL)
+    {
+      if (!has_location)
+        return;
+
+      marker = create_marker (self, contact);
+    }
+  else if (!has_location)
+    {
+      champlain_base_marker_animate_out (CHAMPLAIN_BASE_MARKER (marker));
+      return;
+    }
+
+  location = empathy_contact_get_location (contact);
 
   value = g_hash_table_lookup (location, EMPATHY_LOCATION_LAT);
   if (value == NULL)
@@ -112,9 +142,9 @@ map_view_marker_update_position (ChamplainMarker *marker,
 static void
 map_view_contact_location_notify (EmpathyContact *contact,
     GParamSpec *arg1,
-    ChamplainMarker *marker)
+    EmpathyMapView *self)
 {
-  map_view_marker_update_position (marker, contact);
+  map_view_update_contact_position (self, contact);
 }
 
 static void
@@ -223,30 +253,14 @@ map_view_contacts_update_label (ChamplainMarker *marker)
   g_free (label);
 }
 
-static gboolean
-map_view_contacts_foreach (GtkTreeModel *model,
-    GtkTreePath *path,
-    GtkTreeIter *iter,
-    gpointer user_data)
+static ChamplainMarker *
+create_marker (EmpathyMapView *window,
+    EmpathyContact *contact)
 {
-  EmpathyMapView *window = (EmpathyMapView *) user_data;
-  EmpathyContact *contact;
   ClutterActor *marker;
   ClutterActor *texture;
-  GHashTable *location;
   GdkPixbuf *avatar;
 
-  gtk_tree_model_get (model, iter, EMPATHY_CONTACT_LIST_STORE_COL_CONTACT,
-     &contact, -1);
-
-  if (contact == NULL)
-    return FALSE;
-
-  location = empathy_contact_get_location (contact);
-
-  if (location == NULL || g_hash_table_size (location) == 0)
-    return FALSE;
-
   marker = champlain_marker_new ();
 
   avatar = empathy_pixbuf_avatar_from_contact_scaled (contact, 32, 32);
@@ -264,6 +278,8 @@ map_view_contacts_foreach (GtkTreeModel *model,
   g_object_set_data_full (G_OBJECT (marker), "contact",
       g_object_ref (contact), g_object_unref);
 
+  g_hash_table_insert (window->markers, g_object_ref (contact), marker);
+
   map_view_contacts_update_label (CHAMPLAIN_MARKER (marker));
 
   clutter_actor_set_reactive (CLUTTER_ACTOR (marker), TRUE);
@@ -272,10 +288,35 @@ map_view_contacts_foreach (GtkTreeModel *model,
 
   clutter_container_add (CLUTTER_CONTAINER (window->layer), marker, NULL);
 
+  return CHAMPLAIN_MARKER (marker);
+}
+
+static void
+contact_added (EmpathyMapView *window,
+    EmpathyContact *contact)
+{
   g_signal_connect (contact, "notify::location",
-      G_CALLBACK (map_view_contact_location_notify), marker);
+      G_CALLBACK (map_view_contact_location_notify), window);
+
+  map_view_update_contact_position (window, contact);
+}
+
+static gboolean
+map_view_contacts_foreach (GtkTreeModel *model,
+    GtkTreePath *path,
+    GtkTreeIter *iter,
+    gpointer user_data)
+{
+  EmpathyMapView *window = (EmpathyMapView *) user_data;
+  EmpathyContact *contact;
+
+  gtk_tree_model_get (model, iter, EMPATHY_CONTACT_LIST_STORE_COL_CONTACT,
+     &contact, -1);
+
+  if (contact == NULL)
+    return FALSE;
 
-  map_view_marker_update_position (CHAMPLAIN_MARKER (marker), contact);
+  contact_added (window, contact);
 
   g_object_unref (contact);
   return FALSE;
@@ -285,24 +326,21 @@ static void
 map_view_destroy_cb (GtkWidget *widget,
     EmpathyMapView *window)
 {
-  GList *item;
+  GHashTableIter iter;
+  gpointer contact;
+  EmpathyContactList *list_iface;
 
   g_source_remove (window->timeout_id);
 
-  item = clutter_container_get_children (CLUTTER_CONTAINER (window->layer));
-  while (item != NULL)
-  {
-    EmpathyContact *contact;
-    ChamplainMarker *marker;
-
-    marker = CHAMPLAIN_MARKER (item->data);
-    contact = g_object_get_data (G_OBJECT (marker), "contact");
+  g_hash_table_iter_init (&iter, window->markers);
+  while (g_hash_table_iter_next (&iter, &contact, NULL))
     g_signal_handlers_disconnect_by_func (contact,
-        map_view_contact_location_notify, marker);
+        map_view_contact_location_notify, window);
 
-    item = g_list_next (item);
-  }
+  list_iface = empathy_contact_list_store_get_list_iface (window->list_store);
+  g_signal_handler_disconnect (list_iface, window->members_changed_id);
 
+  g_hash_table_destroy (window->markers);
   g_object_unref (window->list_store);
   g_object_unref (window->layer);
   g_slice_free (EmpathyMapView, window);
@@ -336,6 +374,39 @@ map_view_tick (EmpathyMapView *window)
   return TRUE;
 }
 
+static void
+contact_removed (EmpathyMapView *self,
+    EmpathyContact *contact)
+{
+  ClutterActor *marker;
+
+  marker = g_hash_table_lookup (self->markers, contact);
+  if (marker == NULL)
+    return;
+
+  clutter_actor_destroy (marker);
+  g_hash_table_remove (self->markers, contact);
+}
+
+static void
+members_changed_cb (EmpathyContactList *list,
+    EmpathyContact *contact,
+    EmpathyContact *actor,
+    guint reason,
+    gchar *message,
+    gboolean is_member,
+    EmpathyMapView *self)
+{
+  if (is_member)
+    {
+      contact_added (self, contact);
+    }
+  else
+    {
+      contact_removed (self, contact);
+    }
+}
+
 GtkWidget *
 empathy_map_view_show (void)
 {
@@ -387,6 +458,9 @@ empathy_map_view_show (void)
   empathy_contact_list_store_set_show_avatars (list_store, TRUE);
   g_object_unref (list_iface);
 
+  window->members_changed_id = g_signal_connect (list_iface, "members-changed",
+      G_CALLBACK (members_changed_cb), window);
+
   window->throbber = ephy_spinner_new ();
   ephy_spinner_set_size (EPHY_SPINNER (window->throbber),
       GTK_ICON_SIZE_LARGE_TOOLBAR);
@@ -412,6 +486,9 @@ empathy_map_view_show (void)
       G_CALLBACK (map_view_state_changed), window);
 
   /* Set up contact list. */
+  window->markers = g_hash_table_new_full (NULL, NULL,
+      (GDestroyNotify) g_object_unref, NULL);
+
   model = GTK_TREE_MODEL (window->list_store);
   gtk_tree_model_foreach (model, map_view_contacts_foreach, window);
 
