diff --git a/plugins/telephony/conversationsdbusinterface.cpp b/plugins/telephony/conversationsdbusinterface.cpp
index 976ec72f..345ddbb9 100644
--- a/plugins/telephony/conversationsdbusinterface.cpp
+++ b/plugins/telephony/conversationsdbusinterface.cpp
@@ -1,122 +1,134 @@
 /**
  * Copyright 2018 Simon Redman <simon@ergotech.com>
  *
  * This program is free software; you can redistribute it and/or
  * modify it under the terms of the GNU General Public License as
  * published by the Free Software Foundation; either version 2 of
  * the License or (at your option) version 3 or any later version
  * accepted by the membership of KDE e.V. (or its successor approved
  * by the membership of KDE e.V.), which shall act as a proxy
  * defined in Section 14 of version 3 of the license.
  *
  * This program is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 #include "conversationsdbusinterface.h"
 #include "interfaces/dbusinterfaces.h"
 #include "interfaces/conversationmessage.h"
 
 #include <QDBusConnection>
 
 #include <core/device.h>
 #include <core/kdeconnectplugin.h>
 
 #include "telephonyplugin.h"
 
 ConversationsDbusInterface::ConversationsDbusInterface(KdeConnectPlugin* plugin)
     : QDBusAbstractAdaptor(const_cast<Device*>(plugin->device()))
     , m_device(plugin->device())
     , m_plugin(plugin)
     , m_lastId(0)
     , m_telephonyInterface(m_device->id())
 {
     ConversationMessage::registerDbusType();
 }
 
 ConversationsDbusInterface::~ConversationsDbusInterface()
 {
 }
 
 QStringList ConversationsDbusInterface::activeConversations()
 {
     return m_conversations.keys();
 }
 
 void ConversationsDbusInterface::requestConversation(const QString& conversationID, int start, int end)
 {
-    const auto messagesList = m_conversations[conversationID];
+    const auto messagesList = m_conversations[conversationID].values();
 
     if (messagesList.isEmpty())
     {
         // Since there are no messages in the conversation, it's likely that it is a junk ID, but go ahead anyway
         qCWarning(KDECONNECT_PLUGIN_TELEPHONY) << "Got a conversationID for a conversation with no messages!" << conversationID;
     }
 
     m_telephonyInterface.requestConversation(conversationID);
 
-    for(int i=start; i<end; ++i) {
-        if (i<messagesList.size()) {
-            Q_EMIT conversationMessageReceived(messagesList.at(i).toVariant(), i);
+    // Messages are sorted in ascending order of keys, meaning the front of the list has the oldest
+    // messages (smallest timestamp number)
+    // Therefore, return the end of the list first (most recent messages)
+    int i = start;
+    for(auto it = messagesList.crbegin(); it != messagesList.crend(); ++it)
+    {
+        Q_EMIT conversationMessageReceived(it->toVariant(), i);
+        i++;
+        if (i >= end)
+        {
+            break;
         }
     }
 }
 
 void ConversationsDbusInterface::addMessage(const ConversationMessage &message)
 {
     const QString& threadId = QString::number(message.threadID());
 
     if (m_known_messages[threadId].contains(message.uID()))
     {
         // This message has already been processed. Don't do anything.
         return;
     }
 
     // Store the Message in the list corresponding to its thread
     bool newConversation = !m_conversations.contains(threadId);
-    m_conversations[threadId].append(message);
+    m_conversations[threadId].insert(message.date(), message);
     m_known_messages[threadId].insert(message.uID());
 
     // Tell the world about what just happened
     if (newConversation)
     {
         Q_EMIT conversationCreated(threadId);
     } else
     {
         Q_EMIT conversationUpdated(threadId);
     }
 }
 
 void ConversationsDbusInterface::removeMessage(const QString& internalId)
 {
     // TODO: Delete the specified message from our internal structures
 }
 
 void ConversationsDbusInterface::replyToConversation(const QString& conversationID, const QString& message)
 {
     const auto messagesList = m_conversations[conversationID];
     if (messagesList.isEmpty())
     {
         // Since there are no messages in the conversation, we can't do anything sensible
         qCWarning(KDECONNECT_PLUGIN_TELEPHONY) << "Got a conversationID for a conversation with no messages!";
         return;
     }
-    const QString& address = messagesList.front().address();
+    // Caution:
+    // This method assumes that the address of any message (in this case, whichever one pops out
+    // with .first()) will be the same. This works fine for single-target SMS but might break down
+    // for group MMS, etc.
+    const QString& address = messagesList.first().address();
     m_telephonyInterface.sendSms(address, message);
 }
 
 void ConversationsDbusInterface::requestAllConversationThreads()
 {
     // Prepare the list of conversations by requesting the first in every thread
     m_telephonyInterface.requestAllConversations();
 }
 
 QString ConversationsDbusInterface::newId()
 {
     return QString::number(++m_lastId);
 }
diff --git a/plugins/telephony/conversationsdbusinterface.h b/plugins/telephony/conversationsdbusinterface.h
index a2e5c6cc..2270caf4 100644
--- a/plugins/telephony/conversationsdbusinterface.h
+++ b/plugins/telephony/conversationsdbusinterface.h
@@ -1,97 +1,101 @@
 /**
  * Copyright 2013 Albert Vaca <albertvaka@gmail.com>
  *
  * This program is free software; you can redistribute it and/or
  * modify it under the terms of the GNU General Public License as
  * published by the Free Software Foundation; either version 2 of
  * the License or (at your option) version 3 or any later version
  * accepted by the membership of KDE e.V. (or its successor approved
  * by the membership of KDE e.V.), which shall act as a proxy
  * defined in Section 14 of version 3 of the license.
  *
  * This program is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 #ifndef CONVERSATIONSDBUSINTERFACE_H
 #define CONVERSATIONSDBUSINTERFACE_H
 
 #include <QDBusAbstractAdaptor>
 #include <QHash>
 #include <QList>
+#include <QMap>
 #include <QString>
 #include <QStringList>
 #include <QDir>
 #include <QPointer>
 
 #include "interfaces/conversationmessage.h"
 #include "interfaces/dbusinterfaces.h"
 
 class KdeConnectPlugin;
 class Device;
 
 class ConversationsDbusInterface
     : public QDBusAbstractAdaptor
 {
     Q_OBJECT
     Q_CLASSINFO("D-Bus Interface", "org.kde.kdeconnect.device.conversations")
 
 public:
     explicit ConversationsDbusInterface(KdeConnectPlugin* plugin);
     ~ConversationsDbusInterface() override;
 
     void addMessage(const ConversationMessage &message);
     void removeMessage(const QString& internalId);
 
 public Q_SLOTS:
     /**
      * Return a list of the threadID for all valid conversations
      */
     QStringList activeConversations();
 
     void requestConversation(const QString &conversationID, int start, int end);
 
     /**
      * Send a new message to this conversation
      */
     void replyToConversation(const QString& conversationID, const QString& message);
 
     /**
      * Send the request to the Telephony plugin to update the list of conversation threads
      */
     void requestAllConversationThreads();
 
 Q_SIGNALS:
     Q_SCRIPTABLE void conversationCreated(const QString& threadID);
     Q_SCRIPTABLE void conversationRemoved(const QString& threadID);
     Q_SCRIPTABLE void conversationUpdated(const QString& threadID);
     Q_SCRIPTABLE void conversationMessageReceived(const QVariantMap & msg, int pos) const;
 
 private /*methods*/:
     QString newId(); //Generates successive identifitiers to use as public ids
 
 private /*attributes*/:
     const Device* m_device;
     KdeConnectPlugin* m_plugin;
 
     /**
-     * Mapping of threadID to the list of messages which make up that thread
+     * Mapping of threadID to the messages which make up that thread
+     *
+     * The messages are stored as a QMap of the timestamp to the actual message object so that
+     * we can use .values() to get a sorted list of messages from least- to most-recent
      */
-    QHash<QString, QVector<ConversationMessage>> m_conversations;
+    QHash<QString, QMap<qint64, ConversationMessage>> m_conversations;
 
     /**
      * Mapping of threadID to the set of uIDs known in the corresponding conversation
      */
     QHash<QString, QSet<qint32>> m_known_messages;
 
     int m_lastId;
 
     TelephonyDbusInterface m_telephonyInterface;
 };
 
 #endif // CONVERSATIONSDBUSINTERFACE_H