diff --git a/backends/key-file/kf-persona-store.vala b/backends/key-file/kf-persona-store.vala
index 425b559..831a186 100644
--- a/backends/key-file/kf-persona-store.vala
+++ b/backends/key-file/kf-persona-store.vala
@@ -32,6 +32,7 @@ public class Folks.Backends.Kf.PersonaStore : Folks.PersonaStore
   private HashTable<string, Persona> _personas;
   private File file;
   private GLib.KeyFile key_file;
+  private uint first_unused_id = 0;
 
   /**
    * {@inheritDoc}
@@ -139,6 +140,9 @@ public class Folks.Backends.Kf.PersonaStore : Folks.PersonaStore
       string[] groups = this.key_file.get_groups ();
       foreach (string persona_uid in groups)
         {
+          if (persona_uid.to_int () == this.first_unused_id)
+            this.first_unused_id++;
+
           Persona persona = new Kf.Persona (this.key_file, persona_uid, this);
           this._personas.insert (persona.iid, persona);
         }
@@ -173,33 +177,26 @@ public class Folks.Backends.Kf.PersonaStore : Folks.PersonaStore
   public override async Folks.Persona? add_persona_from_details (
       HashTable<string, Value?> details) throws Folks.PersonaStoreError
     {
-      Value val = details.lookup ("im-address");
-      unowned string im_address = val.get_string ();
-      val = details.lookup ("protocol");
-      unowned string protocol = val.get_string ();
+      unowned Value val = details.lookup ("im-addresses");
+      unowned HashTable<string, GenericArray<string>> im_addresses =
+          (HashTable<string, GenericArray<string>>) val.get_boxed ();
 
-      if (im_address == null || protocol == null)
+      if (im_addresses == null || im_addresses.size () == 0)
         {
           throw new PersonaStoreError.INVALID_ARGUMENT (
               "persona store (%s, %s) requires the following details:\n" +
-              "    im-address (provided: '%s')\n",
-              "    protocol (provided: '%s')\n",
-              this.type_id, this.id, im_address, protocol);
+              "    im-addresses (provided: '%p')\n",
+              this.type_id, this.id, im_addresses);
         }
 
-      /* Take the persona ID as the concatenation of the protocol and IM
-       * address, fairly arbitrarily */
-      string persona_id = protocol + ":" + im_address;
-
-      /* Insert the new IM details into the key file and create a Persona from
-       * them */
-      string[] im_addresses = new string[1];
-      im_addresses[0] = im_address;
-      this.key_file.set_string_list (persona_id, protocol, im_addresses);
-      yield this.save_key_file ();
+      string persona_id = this.first_unused_id.to_string ();
+      this.first_unused_id++;
 
+      /* Create a new persona and set its im-addresses property to update the
+       * key file */
       Persona persona = new Kf.Persona (this.key_file, persona_id, this);
       this._personas.insert (persona.iid, persona);
+      persona.im_addresses = im_addresses;
 
       /* FIXME: Groups.ChangeReason is not the right enum to use here */
       GLib.List<Persona> personas = new GLib.List<Persona> ();
diff --git a/backends/key-file/kf-persona.vala b/backends/key-file/kf-persona.vala
index df5b935..c3133d5 100644
--- a/backends/key-file/kf-persona.vala
+++ b/backends/key-file/kf-persona.vala
@@ -65,8 +65,10 @@ public class Folks.Backends.Kf.Persona : Folks.Persona,
           this._im_addresses.foreach ((k, v) =>
             {
               unowned string protocol = (string) k;
-              unowned string[] addresses = (string[]) v;
-              this.key_file.set_string_list (this.uid, protocol, addresses);
+              unowned PtrArray addresses = (PtrArray) v;
+              unowned string[] _addresses = (string[]) addresses.pdata;
+              _addresses.length = (int) addresses.len;
+              this.key_file.set_string_list (this.uid, protocol, _addresses);
             });
 
           /* Get the PersonaStore to save the key file */
@@ -118,9 +120,12 @@ public class Folks.Backends.Kf.Persona : Folks.Persona,
         }
       catch (KeyFileError e)
         {
-          /* This should never be reached, as we're listing the keys then
-           * iterating through the list. */
-          GLib.assert_not_reached ();
+          /* We get a GROUP_NOT_FOUND exception if we're creating a new
+           * Persona, since it doesn't yet exist in the key file. We shouldn't
+           * get any other exceptions, since we're iterating through a list of
+           * keys we've just retrieved. */
+          if (!(e is KeyFileError.GROUP_NOT_FOUND))
+            GLib.assert_not_reached ();
         }
     }
 
diff --git a/backends/telepathy/tpf-persona.vala b/backends/telepathy/tpf-persona.vala
index 5acb443..f7f0c9d 100644
--- a/backends/telepathy/tpf-persona.vala
+++ b/backends/telepathy/tpf-persona.vala
@@ -37,11 +37,13 @@ public class Tpf.Persona : Folks.Persona,
     Avatar,
     Favourite,
     Groups,
+    IMable,
     Presence
 {
   private HashTable<string, bool> _groups;
   private bool _is_favourite;
   private string _alias;
+  private HashTable<string, GenericArray<string>> _im_addresses;
 
   /* Whether we've finished being constructed; this is used to prevent
    * unnecessary trips to the Telepathy service to tell it about properties
@@ -103,6 +105,15 @@ public class Tpf.Persona : Folks.Persona,
   /**
    * {@inheritDoc}
    */
+  public HashTable<string, GenericArray<string>> im_addresses
+    {
+      get { return this._im_addresses; }
+      private set {}
+    }
+
+  /**
+   * {@inheritDoc}
+   */
   public HashTable<string, bool> groups
     {
       get { return this._groups; }
@@ -170,6 +181,8 @@ public class Tpf.Persona : Folks.Persona,
    */
   public Persona (Contact contact, PersonaStore store) throws Tpf.PersonaError
     {
+      string[] linkable_properties = { "im-addresses" };
+
       /* FIXME: There is the possibility of a crash in the error condition below
        * due to bgo#604299, where the C self variable isn't initialised until we
        * chain up to the Object constructor, below. */
@@ -194,12 +207,22 @@ public class Tpf.Persona : Folks.Persona,
                * bgo#624842 being fixed. */
               iid: account.get_protocol () + ":" + id,
               uid: uid,
-              store: store);
+              store: store,
+              linkable_properties: linkable_properties);
 
       debug ("Creating new Tpf.Persona '%s' for service-specific UID '%s': %p",
           uid, id, this);
       this.is_constructed = true;
 
+      /* Set our single IM address */
+      GenericArray<string> im_address_array = new GenericArray<string> ();
+      im_address_array.add (id);
+
+      this._im_addresses =
+          new HashTable<string, GenericArray<string>> (str_hash, str_equal);
+      this._im_addresses.insert (account.get_protocol (), im_address_array);
+
+      /* Groups */
       this._groups = new HashTable<string, bool> (str_hash, str_equal);
 
       contact.notify["avatar-file"].connect ((s, p) =>
diff --git a/folks/individual-aggregator.vala b/folks/individual-aggregator.vala
index f12270a..0ba2a7e 100644
--- a/folks/individual-aggregator.vala
+++ b/folks/individual-aggregator.vala
@@ -36,6 +36,12 @@ public errordomain Folks.IndividualAggregatorError
    * Adding a {@link Persona} to a {@link PersonaStore} failed.
    */
   ADD_FAILED,
+
+  /**
+   * An operation which required the use of a writeable store failed because no
+   * writeable store was available.
+   */
+  NO_WRITEABLE_STORE,
 }
 
 /**
@@ -47,6 +53,7 @@ public class Folks.IndividualAggregator : Object
 {
   private BackendStore backend_store;
   private HashMap<string, PersonaStore> stores;
+  private unowned PersonaStore writeable_store;
   private HashSet<Backend> backends;
   private HashTable<string, Individual> link_map;
 
@@ -157,6 +164,7 @@ public class Folks.IndividualAggregator : Object
       if (store.type_id == "key-file")
         {
           store.trust_level = PersonaStoreTrust.FULL;
+          this.writeable_store = store;
         }
 
       this.stores.set (store_id, store);
@@ -183,10 +191,12 @@ public class Folks.IndividualAggregator : Object
       store.personas_changed.disconnect (this.personas_changed_cb);
       store.notify["trust-level"].disconnect (this.trust_level_changed_cb);
 
-      /* no need to remove this stores' personas from all the individuals, since
+      /* no need to remove this store's personas from all the individuals, since
        * they'll do that themselves (and emit their own 'removed' signal if
        * necessary) */
 
+      if (this.writeable_store == store)
+        this.writeable_store = null;
       this.stores.unset (this.get_store_full_id (store.type_id, store.id));
     }
 
@@ -495,4 +505,80 @@ public class Folks.IndividualAggregator : Object
     {
       yield persona.store.remove_persona (persona);
     }
+
+  /* FIXME: This should be GLib.List<Persona>, but Vala won't allow it */
+  public async void link_personas (void *_personas)
+      throws GLib.Error
+    {
+      unowned GLib.List<Persona> personas = (GLib.List<Persona>) _personas;
+
+      if (this.writeable_store == null)
+        {
+          throw new IndividualAggregatorError.NO_WRITEABLE_STORE (
+              "Can't link personas with no writeable store.");
+        }
+
+      /* Don't bother linking if it's just one Persona */
+      if (personas.next == null)
+        return;
+
+      /* Create a new persona in the writeable store which links together the
+       * given personas */
+      /* FIXME: We hardcode this to use the key-file backend for now */
+      assert (this.writeable_store.type_id == "key-file");
+
+      HashTable<string, GenericArray<string>> protocols =
+          new HashTable<string, GenericArray<string>> (str_hash, str_equal);
+      personas.foreach ((p) =>
+        {
+          unowned Persona persona = (Persona) p;
+
+          if (!(Persona is IMable))
+            return;
+
+          ((IMable) persona).im_addresses.foreach ((k, v) =>
+            {
+              unowned string protocol = (string) k;
+              unowned GenericArray<string> addresses = (GenericArray<string>) v;
+
+              GenericArray<string> existing_addresses =
+                  protocols.lookup (protocol);
+              if (existing_addresses == null)
+                {
+                  existing_addresses = new GenericArray<string> ();
+                  protocols.insert (protocol, existing_addresses);
+                }
+
+              addresses.foreach ((a) =>
+                {
+                  unowned string address = (string) a;
+                  existing_addresses.add (address);
+                });
+            });
+        });
+
+      Value addresses_value = Value (typeof (HashTable));
+      addresses_value.set_boxed (protocols);
+
+      HashTable<string, Value?> details =
+          new HashTable<string, Value?> (str_hash, str_equal);
+      details.insert ("im-addresses", addresses_value);
+
+      yield this.add_persona_from_details (null, this.writeable_store.type_id,
+          this.writeable_store.id, details);
+    }
+
+  public async void unlink_individual (Individual individual) throws GLib.Error
+    {
+      /* Remove all the Personas from writeable PersonaStores
+       * We have to iterate manually since using foreach() requires a sync
+       * lambda function, meaning we can't yield on the remove_persona() call */
+      unowned GLib.List<unowned Persona> i;
+      for (i = individual.personas; i != null; i = i.next)
+        {
+          unowned Persona persona = (Persona) i.data;
+          if (persona.store == this.writeable_store)
+            yield this.writeable_store.remove_persona (persona);
+        }
+    }
 }
diff --git a/folks/individual.vala b/folks/individual.vala
index 695cad7..341d541 100644
--- a/folks/individual.vala
+++ b/folks/individual.vala
@@ -147,6 +147,12 @@ public class Folks.Individual : Object,
    *
    * Changing the set of personas may cause updates to the aggregated properties
    * provided by the Individual, resulting in property notifications for them.
+   *
+   * Changing the set of personas will not cause permanent linking/unlinking of
+   * the added/removed personas to/from this Individual. To do that, call
+   * {@link IndividualAggregator.link_personas} or
+   * {@link IndividualAggregator.unlink_individual}, which will ensure the link
+   * changes are written to the appropriate backend.
    */
   public GLib.List<Persona> personas
     {
