diff --git a/lib/kolab_sync_storage.php b/lib/kolab_sync_storage.php
--- a/lib/kolab_sync_storage.php
+++ b/lib/kolab_sync_storage.php
@@ -56,7 +56,7 @@
     protected $folders = [];
     protected $root_meta;
     protected $relations = [];
-    protected $relationSupport = true;
+    public $relationSupport = true;
     protected $tag_rts = [];
     private $modseq = [];
 
diff --git a/lib/kolab_sync_storage_kolab4.php b/lib/kolab_sync_storage_kolab4.php
--- a/lib/kolab_sync_storage_kolab4.php
+++ b/lib/kolab_sync_storage_kolab4.php
@@ -29,7 +29,7 @@
 class kolab_sync_storage_kolab4 extends kolab_sync_storage
 {
     protected $davStorage = null;
-    protected $relationSupport = false;
+    public $relationSupport = false;
 
     /**
      * This implements the 'singleton' design pattern
diff --git a/tests/Sync/Sync/RelationsTest.php b/tests/Sync/Sync/RelationsTest.php
new file mode 100644
--- /dev/null
+++ b/tests/Sync/Sync/RelationsTest.php
@@ -0,0 +1,202 @@
+<?php
+
+namespace Tests\Sync\Sync;
+
+class RelationsTest extends \Tests\SyncTestCase
+{
+
+    protected function initialSyncRequest($folderId) {
+        $request = <<<EOF
+            <?xml version="1.0" encoding="utf-8"?>
+            <!DOCTYPE AirSync PUBLIC "-//AIRSYNC//DTD AirSync//EN" "http://www.microsoft.com/">
+            <Sync xmlns="uri:AirSync">
+                <Collections>
+                    <Collection>
+                        <SyncKey>0</SyncKey>
+                        <CollectionId>{$folderId}</CollectionId>
+                    </Collection>
+                </Collections>
+            </Sync>
+            EOF;
+        return $this->request($request, 'Sync');
+    }
+
+    protected function syncRequest($syncKey, $folderId, $windowSize = null) {
+        $request = <<<EOF
+            <?xml version="1.0" encoding="utf-8"?>
+            <!DOCTYPE AirSync PUBLIC "-//AIRSYNC//DTD AirSync//EN" "http://www.microsoft.com/">
+            <Sync xmlns="uri:AirSync" xmlns:AirSyncBase="uri:AirSyncBase">
+                <Collections>
+                    <Collection>
+                        <SyncKey>{$syncKey}</SyncKey>
+                        <CollectionId>{$folderId}</CollectionId>
+                        <DeletesAsMoves>1</DeletesAsMoves>
+                        <GetChanges>1</GetChanges>
+                        <WindowSize>{$windowSize}</WindowSize>
+                        <Options>
+                            <FilterType>0</FilterType>
+                            <Conflict>1</Conflict>
+                            <BodyPreference xmlns="uri:AirSyncBase">
+                                <Type>2</Type>
+                                <TruncationSize>51200</TruncationSize>
+                                <AllOrNone>0</AllOrNone>
+                            </BodyPreference>
+                        </Options>
+                    </Collection>
+                </Collections>
+            </Sync>
+            EOF;
+        return $this->request($request, 'Sync');
+    }
+
+    /**
+     * Test Sync command
+     */
+    public function testRelationsSync()
+    {
+        $sync = \kolab_sync::get_instance();
+        if (!$sync->storage()->relationSupport) {
+            $this->markTestSkipped('No relation support');
+        }
+
+        $this->emptyTestFolder('INBOX', 'mail');
+        $this->emptyTestFolder('Configuration', 'configuration');
+        $this->registerDevice();
+
+        // Test INBOX
+        $folderId = '38b950ebd62cd9a66929c89615d0fc04';
+        $syncKey = 0;
+        $response = $this->initialSyncRequest($folderId);
+        $this->assertEquals(200, $response->getStatusCode());
+
+        $dom = $this->fromWbxml($response->getBody());
+        $xpath = $this->xpath($dom);
+
+        $this->assertSame('1', $xpath->query("//ns:Sync/ns:Collections/ns:Collection/ns:Status")->item(0)->nodeValue);
+        $this->assertSame(strval(++$syncKey), $xpath->query("//ns:Sync/ns:Collections/ns:Collection/ns:SyncKey")->item(0)->nodeValue);
+        $this->assertSame('Email', $xpath->query("//ns:Sync/ns:Collections/ns:Collection/ns:Class")->item(0)->nodeValue);
+        $this->assertSame($folderId, $xpath->query("//ns:Sync/ns:Collections/ns:Collection/ns:CollectionId")->item(0)->nodeValue);
+
+        // First we append 
+        $uid1 = $this->appendMail('INBOX', 'mail.sync1');
+        $uid2 = $this->appendMail('INBOX', 'mail.sync2');
+        $this->appendMail('INBOX', 'mail.sync1', ['sync1' => 'sync3']);
+        $this->appendMail('INBOX', 'mail.sync1', ['sync1' => 'sync4']);
+
+        $sync = \kolab_sync::get_instance();
+
+        $device = $sync->storage()->device_get(self::$deviceId);
+
+        //Add a tag
+        $sync->storage()->updateItem($folderId, $device['ID'], \kolab_sync_storage::MODEL_EMAIL, $uid1, null, ['categories' => ['test1']]);
+        sleep(1);
+
+        $response = $this->syncRequest($syncKey, $folderId, 10);
+        $this->assertEquals(200, $response->getStatusCode());
+        $dom = $this->fromWbxml($response->getBody());
+        $xpath = $this->xpath($dom);
+        $root = "//ns:Sync/ns:Collections/ns:Collection";
+        $this->assertSame('1', $xpath->query("{$root}/ns:Status")->item(0)->nodeValue);
+        $this->assertSame(strval(++$syncKey), $xpath->query("{$root}/ns:SyncKey")->item(0)->nodeValue);
+        $this->assertSame($folderId, $xpath->query("{$root}/ns:CollectionId")->item(0)->nodeValue);
+        $this->assertSame(4, $xpath->query("{$root}/ns:Commands/ns:Add")->count());
+
+        $root .= "/ns:Commands/ns:Add";
+        $this->assertSame(1, $xpath->query("{$root}/ns:ApplicationData/Email:Categories")->count());
+        $this->assertSame("test1", $xpath->query("{$root}/ns:ApplicationData/Email:Categories")->item(0)->nodeValue);
+
+        //Add a second tag
+        $sync->storage()->updateItem($folderId, $device['ID'], \kolab_sync_storage::MODEL_EMAIL, $uid1, null, ['categories' => ['test1', 'test2']]);
+        sleep(1); // Necessary to make sure we pick up on the tag.
+
+        $response = $this->syncRequest($syncKey, $folderId, 10);
+        $this->assertEquals(200, $response->getStatusCode());
+        $dom = $this->fromWbxml($response->getBody());
+        $xpath = $this->xpath($dom);
+
+        $root = "//ns:Sync/ns:Collections/ns:Collection";
+        $this->assertSame('1', $xpath->query("{$root}/ns:Status")->item(0)->nodeValue);
+        $this->assertSame(strval(++$syncKey), $xpath->query("{$root}/ns:SyncKey")->item(0)->nodeValue);
+        $this->assertSame($folderId, $xpath->query("{$root}/ns:CollectionId")->item(0)->nodeValue);
+        $this->assertSame(0, $xpath->query("{$root}/ns:Commands/ns:Add")->count());
+        $this->assertSame(1, $xpath->query("{$root}/ns:Commands/ns:Change")->count());
+        $root .= "/ns:Commands/ns:Change";
+        $this->assertSame(1, $xpath->query("{$root}/ns:ApplicationData/Email:Categories")->count());
+        //FIXME not sure what I'm doing wrong, but the xml looks ok
+        $this->assertSame("test1test2", $xpath->query("{$root}/ns:ApplicationData/Email:Categories")->item(0)->nodeValue);
+
+        //Rerun the same command and make sure we get the same result
+        $syncKey--;
+        $root = "//ns:Sync/ns:Collections/ns:Collection";
+        $this->assertSame('1', $xpath->query("{$root}/ns:Status")->item(0)->nodeValue);
+        $this->assertSame(strval(++$syncKey), $xpath->query("{$root}/ns:SyncKey")->item(0)->nodeValue);
+        $this->assertSame($folderId, $xpath->query("{$root}/ns:CollectionId")->item(0)->nodeValue);
+        $this->assertSame(0, $xpath->query("{$root}/ns:Commands/ns:Add")->count());
+        $this->assertSame(1, $xpath->query("{$root}/ns:Commands/ns:Change")->count());
+        $root .= "/ns:Commands/ns:Change";
+        $this->assertSame(1, $xpath->query("{$root}/ns:ApplicationData/Email:Categories")->count());
+        //FIXME not sure what I'm doing wrong, but the xml looks ok
+        $this->assertSame("test1test2", $xpath->query("{$root}/ns:ApplicationData/Email:Categories")->item(0)->nodeValue);
+
+
+        // Assert the db state
+        $rcube = \rcube::get_instance();
+        $db    = $rcube->get_dbh();
+        $result = $db->query(
+            "SELECT `data`, `synctime` FROM `syncroton_relations_state`"
+            . " WHERE `device_id` = ? AND `folder_id` = ?"
+            . " ORDER BY `synctime` DESC",
+            $device['ID'],
+            $folderId
+        );
+        $data = [];
+        while ($state = $db->fetch_assoc($result)) {
+            $data[] = $state;
+        }
+        $this->assertSame(1, count($data));
+
+        // Reset to no tags
+        $sync->storage()->updateItem($folderId, $device['ID'], \kolab_sync_storage::MODEL_EMAIL, $uid1, null, ['categories' => []]);
+        sleep(1); // Necessary to make sure we pick up on the tag.
+
+        $response = $this->syncRequest($syncKey, $folderId, 10);
+        $this->assertEquals(200, $response->getStatusCode());
+        $dom = $this->fromWbxml($response->getBody());
+        $xpath = $this->xpath($dom);
+
+        $root = "//ns:Sync/ns:Collections/ns:Collection";
+        $this->assertSame('1', $xpath->query("{$root}/ns:Status")->item(0)->nodeValue);
+        $this->assertSame(strval(++$syncKey), $xpath->query("{$root}/ns:SyncKey")->item(0)->nodeValue);
+        $this->assertSame($folderId, $xpath->query("{$root}/ns:CollectionId")->item(0)->nodeValue);
+        $this->assertSame(0, $xpath->query("{$root}/ns:Commands/ns:Add")->count());
+        $this->assertSame(1, $xpath->query("{$root}/ns:Commands/ns:Change")->count());
+        $root .= "/ns:Commands/ns:Change";
+        $this->assertSame(0, $xpath->query("{$root}/ns:ApplicationData/Email:Categories")->count());
+        //FIXME this currently fails because we omit the empty categories element
+        // $this->assertSame("", $xpath->query("{$root}/ns:ApplicationData/Email:Categories")->item(0)->nodeValue);
+        
+
+        // Assert the db state
+        $result = $db->query(
+            "SELECT `data`, `synctime` FROM `syncroton_relations_state`"
+            . " WHERE `device_id` = ? AND `folder_id` = ?"
+            . " ORDER BY `synctime` DESC",
+            $device['ID'],
+            $folderId
+        );
+        $data = [];
+        while ($state = $db->fetch_assoc($result)) {
+            $data[] = $state;
+        }
+        $this->assertSame(1, count($data));
+
+        $response = $this->syncRequest($syncKey, $folderId, 10);
+        $this->assertEquals(200, $response->getStatusCode());
+        // We expect an empty response without a change
+        $this->assertEquals(0, $response->getBody()->getSize());
+        // print($dom->saveXML());
+
+        return $syncKey;
+    }
+}
+
diff --git a/tests/SyncTestCase.php b/tests/SyncTestCase.php
--- a/tests/SyncTestCase.php
+++ b/tests/SyncTestCase.php
@@ -51,6 +51,7 @@
         $db->query('DELETE FROM syncroton_data');
         $db->query('DELETE FROM syncroton_data_folder');
         $db->query('DELETE FROM syncroton_content');
+        $db->query('DELETE FROM syncroton_relations_state');
 
         self::$client = new \GuzzleHttp\Client([
                 'http_errors' => false,
@@ -87,6 +88,7 @@
             $db->query('DELETE FROM syncroton_device');
             $db->query('DELETE FROM syncroton_synckey');
             $db->query('DELETE FROM syncroton_folder');
+            $db->query('DELETE FROM syncroton_relations_state');
         }
     }
 
@@ -116,7 +118,7 @@
         $uid = $imap->save_message($folder, $source, '', $is_file);
 
         if ($uid === false) {
-            exit("Failed to append mail into {$folder}");
+            exit("Failed to append mail {$filename} into {$folder}");
         }
 
         return $uid;