diff --git a/patchwork/models.py b/patchwork/models.py
index a043844d51f9..70c9c5a4406b 100644
--- a/patchwork/models.py
+++ b/patchwork/models.py
@@ -324,6 +324,12 @@ class EmailMixin(models.Model):
         return ''.join([match.group(0) + '\n' for match in
                         self.response_re.finditer(self.content)])
 
+    @property
+    def url_msgid(self):
+        """A trimmed messageid, suitable for inclusion in URLs"""
+        assert self.msgid[0] == '<' and self.msgid[-1] == '>'
+        return self.msgid[1:-1]
+
     def save(self, *args, **kwargs):
         # Modifying a submission via admin interface changes '\n' newlines in
         # message content to '\r\n'. We need to fix them to avoid problems,
@@ -380,10 +386,14 @@ class Submission(FilenameMixin, EmailMixin, models.Model):
 class CoverLetter(Submission):
 
     def get_absolute_url(self):
-        return reverse('cover-detail', kwargs={'cover_id': self.id})
+        return reverse('cover-detail',
+                       kwargs={'project_id': self.project.linkname,
+                               'msgid': self.url_msgid})
 
     def get_mbox_url(self):
-        return reverse('cover-mbox', kwargs={'cover_id': self.id})
+        return reverse('cover-mbox',
+                       kwargs={'project_id': self.project.linkname,
+                               'msgid': self.url_msgid})
 
 
 @python_2_unicode_compatible
@@ -552,10 +562,14 @@ class Patch(Submission):
         return counts
 
     def get_absolute_url(self):
-        return reverse('patch-detail', kwargs={'patch_id': self.id})
+        return reverse('patch-detail',
+                       kwargs={'project_id': self.project.linkname,
+                               'msgid': self.url_msgid})
 
     def get_mbox_url(self):
-        return reverse('patch-mbox', kwargs={'patch_id': self.id})
+        return reverse('patch-mbox',
+                       kwargs={'project_id': self.project.linkname,
+                               'msgid': self.url_msgid})
 
     def __str__(self):
         return self.name
@@ -580,7 +594,9 @@ class Comment(EmailMixin, models.Model):
                                    on_delete=models.CASCADE)
 
     def get_absolute_url(self):
-        return reverse('comment-redirect', kwargs={'comment_id': self.id})
+        return reverse('comment-msgid-redirect',
+                       kwargs={'project_id': self.submission.project.linkname,
+                               'msgid': self.url_msgid})
 
     def save(self, *args, **kwargs):
         super(Comment, self).save(*args, **kwargs)
diff --git a/patchwork/templates/patchwork/partials/download-buttons.html b/patchwork/templates/patchwork/partials/download-buttons.html
index 32acf26b6ef7..3c184fb0f384 100644
--- a/patchwork/templates/patchwork/partials/download-buttons.html
+++ b/patchwork/templates/patchwork/partials/download-buttons.html
@@ -4,14 +4,14 @@
       {{ submission.id }}
   </button>
   {% if submission.diff %}
-  <a href="{% url 'patch-raw' patch_id=submission.id %}"
+  <a href="{% url 'patch-raw' project_id=project.linkname msgid=submission.url_msgid %}"
    class="btn btn-default" role="button" title="Download patch diff"
    >diff</a>
-  <a href="{% url 'patch-mbox' patch_id=submission.id %}"
+  <a href="{% url 'patch-mbox' project_id=project.linkname msgid=submission.url_msgid %}"
    class="btn btn-default" role="button" title="Download patch mbox"
    >mbox</a>
   {% else %}
-  <a href="{% url 'cover-mbox' cover_id=submission.id %}"
+  <a href="{% url 'cover-mbox' project_id=project.linkname msgid=submission.url_msgid %}"
    class="btn btn-default" role="button" title="Download cover mbox"
    >mbox</a>
   {% endif %}
diff --git a/patchwork/templates/patchwork/partials/patch-list.html b/patchwork/templates/patchwork/partials/patch-list.html
index 2abb9ec2d019..3754c05c8ac7 100644
--- a/patchwork/templates/patchwork/partials/patch-list.html
+++ b/patchwork/templates/patchwork/partials/patch-list.html
@@ -189,7 +189,7 @@ $(document).ready(function() {
    </td>
    {% endif %}
    <td>
-    <a href="{% url 'patch-detail' patch_id=patch.id %}">
+    <a href="{% url 'patch-detail' project_id=project.linkname msgid=patch.url_msgid %}">
      {{ patch.name|default:"[no subject]"|truncatechars:100 }}
     </a>
    </td>
diff --git a/patchwork/templates/patchwork/submission.html b/patchwork/templates/patchwork/submission.html
index eb5e3583823d..b741af5adcc7 100644
--- a/patchwork/templates/patchwork/submission.html
+++ b/patchwork/templates/patchwork/submission.html
@@ -100,7 +100,7 @@ function toggle_div(link_id, headers_id)
       {% if cover == submission %}
        {{ cover.name|default:"[no subject]"|truncatechars:100 }}
       {% else %}
-      <a href="{% url 'cover-detail' cover_id=cover.id %}">
+      <a href="{% url 'cover-detail' project_id=project.linkname msgid=cover.url_msgid %}">
        {{ cover.name|default:"[no subject]"|truncatechars:100 }}
       </a>
       {% endif %}
@@ -112,7 +112,7 @@ function toggle_div(link_id, headers_id)
       {% if sibling == submission %}
        {{ sibling.name|default:"[no subject]"|truncatechars:100 }}
       {% else %}
-      <a href="{% url 'patch-detail' patch_id=sibling.id %}">
+      <a href="{% url 'patch-detail' project_id=project.linkname msgid=sibling.url_msgid %}">
        {{ sibling.name|default:"[no subject]"|truncatechars:100 }}
       </a>
       {% endif %}
diff --git a/patchwork/tests/test_bundles.py b/patchwork/tests/test_bundles.py
index c88c2a8479fe..e904b11c80a8 100644
--- a/patchwork/tests/test_bundles.py
+++ b/patchwork/tests/test_bundles.py
@@ -457,7 +457,9 @@ class BundleCreateFromPatchTest(BundleTestBase):
                   'action': 'createbundle'}
 
         response = self.client.post(
-            reverse('patch-detail', kwargs={'patch_id': patch.id}), params)
+            reverse('patch-detail',
+                    kwargs={'project_id': patch.project.linkname,
+                            'msgid': patch.url_msgid}), params)
 
         self.assertContains(response,
                             'Bundle %s created' % newbundlename)
@@ -474,7 +476,9 @@ class BundleCreateFromPatchTest(BundleTestBase):
                   'action': 'createbundle'}
 
         response = self.client.post(
-            reverse('patch-detail', kwargs={'patch_id': patch.id}), params)
+            reverse('patch-detail',
+                    kwargs={'project_id': patch.project.linkname,
+                            'msgid': patch.url_msgid}), params)
 
         self.assertContains(
             response,
@@ -585,7 +589,9 @@ class BundleAddFromPatchTest(BundleTestBase):
                   'bundle_id': self.bundle.id}
 
         response = self.client.post(
-            reverse('patch-detail', kwargs={'patch_id': patch.id}), params)
+            reverse('patch-detail',
+                    kwargs={'project_id': patch.project.linkname,
+                            'msgid': patch.url_msgid}), params)
 
         self.assertContains(
             response,
@@ -602,7 +608,9 @@ class BundleAddFromPatchTest(BundleTestBase):
                   'bundle_id': self.bundle.id}
 
         response = self.client.post(
-            reverse('patch-detail', kwargs={'patch_id': patch.id}), params)
+            reverse('patch-detail',
+                    kwargs={'project_id': patch.project.linkname,
+                            'msgid': patch.url_msgid}), params)
 
         self.assertContains(
             response,
diff --git a/patchwork/tests/test_detail.py b/patchwork/tests/test_detail.py
index 9c44779a8293..636b717b906d 100644
--- a/patchwork/tests/test_detail.py
+++ b/patchwork/tests/test_detail.py
@@ -15,10 +15,41 @@ from patchwork.tests.utils import create_series
 class CoverLetterViewTest(TestCase):
 
     def test_redirect(self):
-        patch_id = create_patch().id
+        patch = create_patch()
+
+        requested_url = reverse('cover-detail',
+                                kwargs={'project_id': patch.project.linkname,
+                                        'msgid': patch.url_msgid})
+        redirect_url = reverse('patch-detail',
+                               kwargs={'project_id': patch.project.linkname,
+                                       'msgid': patch.url_msgid})
+
+        response = self.client.get(requested_url)
+        self.assertRedirects(response, redirect_url)
+
+    def test_old_detail_url(self):
+        cover = create_cover()
 
-        requested_url = reverse('cover-detail', kwargs={'cover_id': patch_id})
-        redirect_url = reverse('patch-detail', kwargs={'patch_id': patch_id})
+        requested_url = reverse('cover-id-redirect',
+                                kwargs={'cover_id': cover.id,
+                                        'target': ''})
+        redirect_url = reverse('cover-detail',
+                               kwargs={'project_id': cover.project.linkname,
+                                       'msgid': cover.url_msgid})
+
+        response = self.client.get(requested_url)
+        self.assertRedirects(response, redirect_url)
+
+    def test_old_mbox_url(self):
+        cover = create_cover()
+
+        requested_url = reverse('cover-id-redirect',
+                                kwargs={'cover_id': cover.id,
+                                        'target': '/mbox'})
+        self.assertEqual(requested_url[-6:], '/mbox/')
+        redirect_url = reverse('cover-mbox',
+                               kwargs={'project_id': cover.project.linkname,
+                                       'msgid': cover.url_msgid})
 
         response = self.client.get(requested_url)
         self.assertRedirects(response, redirect_url)
@@ -27,10 +58,14 @@ class CoverLetterViewTest(TestCase):
 class PatchViewTest(TestCase):
 
     def test_redirect(self):
-        cover_id = create_cover().id
+        cover = create_cover()
 
-        requested_url = reverse('patch-detail', kwargs={'patch_id': cover_id})
-        redirect_url = reverse('cover-detail', kwargs={'cover_id': cover_id})
+        requested_url = reverse('patch-detail',
+                                kwargs={'project_id': cover.project.linkname,
+                                        'msgid': cover.url_msgid})
+        redirect_url = reverse('cover-detail',
+                               kwargs={'project_id': cover.project.linkname,
+                                       'msgid': cover.url_msgid})
 
         response = self.client.get(requested_url)
         self.assertRedirects(response, redirect_url)
@@ -43,32 +78,133 @@ class PatchViewTest(TestCase):
             series_.add_patch(patch, 1)
 
         response = self.client.get(
-            reverse('patch-detail', kwargs={'patch_id': patch.id}))
+            reverse('patch-detail',
+                    kwargs={'project_id': patch.project.linkname,
+                            'msgid': patch.url_msgid}))
 
         for series_ in series:
             self.assertContains(
                 response,
                 reverse('series-mbox', kwargs={'series_id': series_.id}))
 
+    def test_old_detail_url(self):
+        patch = create_patch()
+
+        requested_url = reverse('patch-id-redirect',
+                                kwargs={'patch_id': patch.id,
+                                        'target': ''})
+        redirect_url = reverse('patch-detail',
+                               kwargs={'project_id': patch.project.linkname,
+                                       'msgid': patch.url_msgid})
+
+        response = self.client.get(requested_url)
+        self.assertRedirects(response, redirect_url)
+
+    def test_old_mbox_url(self):
+        patch = create_patch()
+
+        requested_url = reverse('patch-id-redirect',
+                                kwargs={'patch_id': patch.id,
+                                        'target': '/mbox'})
+        self.assertEqual(requested_url[-6:], '/mbox/')
+        redirect_url = reverse('patch-mbox',
+                               kwargs={'project_id': patch.project.linkname,
+                                       'msgid': patch.url_msgid})
+
+        response = self.client.get(requested_url)
+        self.assertRedirects(response, redirect_url)
+
+    def test_old_raw_url(self):
+        patch = create_patch()
+
+        requested_url = reverse('patch-id-redirect',
+                                kwargs={'patch_id': patch.id,
+                                        'target': '/raw'})
+        self.assertEqual(requested_url[-5:], '/raw/')
+        redirect_url = reverse('patch-raw',
+                               kwargs={'project_id': patch.project.linkname,
+                                       'msgid': patch.url_msgid})
+
+        response = self.client.get(requested_url)
+        self.assertRedirects(response, redirect_url)
+
 
 class CommentRedirectTest(TestCase):
 
-    def _test_redirect(self, submission, submission_url, submission_id):
+    def _test_redirect(self, submission, submission_url):
         comment_id = create_comment(submission=submission).id
 
         requested_url = reverse('comment-redirect',
                                 kwargs={'comment_id': comment_id})
         redirect_url = '%s#%d' % (
-            reverse(submission_url, kwargs={submission_id: submission.id}),
+            reverse(submission_url,
+                    kwargs={'project_id': submission.project.linkname,
+                            'msgid': submission.url_msgid}),
             comment_id)
 
         response = self.client.get(requested_url)
         self.assertRedirects(response, redirect_url)
 
+    def _test_msgid_redirect(self, submission, submission_url):
+        comment = create_comment(submission=submission)
+
+        requested_url = reverse(
+            'comment-msgid-redirect',
+            kwargs={'msgid': comment.url_msgid,
+                    'project_id': submission.project.linkname})
+
+        redirect_url = '%s#%d' % (
+            reverse(submission_url,
+                    kwargs={'project_id': submission.project.linkname,
+                            'msgid': submission.url_msgid}),
+            comment.id)
+
+        response = self.client.get(requested_url)
+        self.assertRedirects(response, redirect_url)
+
     def test_patch_redirect(self):
         patch = create_patch()
-        self._test_redirect(patch, 'patch-detail', 'patch_id')
+        self._test_redirect(patch, 'patch-detail')
+        self._test_msgid_redirect(patch, 'patch-detail')
 
     def test_cover_redirect(self):
         cover = create_cover()
-        self._test_redirect(cover, 'cover-detail', 'cover_id')
+        self._test_redirect(cover, 'cover-detail')
+        self._test_msgid_redirect(cover, 'cover-detail')
+
+
+class GenericRedirectTest(TestCase):
+
+    def _test_redirect(self, message, view):
+        requested_url = reverse('msgid-redirect',
+                                kwargs={'msgid': message.url_msgid})
+
+        redirect_url = reverse(view,
+                               kwargs={'project_id': message.project.linkname,
+                                       'msgid': message.url_msgid})
+        response = self.client.get(requested_url)
+        self.assertRedirects(response, redirect_url)
+
+    def test_patch(self):
+        patch = create_patch()
+        self._test_redirect(patch, 'patch-detail')
+
+    def test_cover(self):
+        cover = create_cover()
+        self._test_redirect(cover, 'cover-detail')
+
+    def test_comment(self):
+        comment = create_comment()
+        requested_url = reverse('msgid-redirect',
+                                kwargs={'msgid': comment.url_msgid})
+
+        redirect_url = '%s#%d' % (
+            reverse('patch-detail',
+                    kwargs={'project_id': comment.submission.project.linkname,
+                            'msgid': comment.submission.url_msgid}),
+            comment.id)
+
+        # this will redirect twice - once to the comment form, and then
+        # once to the final destination. Hence follow=True.
+        response = self.client.get(requested_url, follow=True)
+        self.assertRedirects(response, redirect_url)
diff --git a/patchwork/tests/test_encodings.py b/patchwork/tests/test_encodings.py
index 883dfc4401f4..be9e6c320dc9 100644
--- a/patchwork/tests/test_encodings.py
+++ b/patchwork/tests/test_encodings.py
@@ -19,16 +19,21 @@ class UTF8PatchViewTest(TestCase):
 
     def test_patch_view(self):
         response = self.client.get(reverse(
-            'patch-detail', args=[self.patch.id]))
+            'patch-detail', args=[self.patch.project.linkname,
+                                  self.patch.url_msgid]))
         self.assertContains(response, self.patch.name)
 
     def test_mbox_view(self):
-        response = self.client.get(reverse('patch-mbox', args=[self.patch.id]))
+        response = self.client.get(
+            reverse('patch-mbox', args=[self.patch.project.linkname,
+                                        self.patch.url_msgid]))
         self.assertEqual(response.status_code, 200)
         self.assertTrue(self.patch.diff in response.content.decode('utf-8'))
 
     def test_raw_view(self):
-        response = self.client.get(reverse('patch-raw', args=[self.patch.id]))
+        response = self.client.get(reverse('patch-raw',
+                                           args=[self.patch.project.linkname,
+                                                 self.patch.url_msgid]))
         self.assertEqual(response.status_code, 200)
         self.assertEqual(response.content.decode('utf-8'), self.patch.diff)
 
diff --git a/patchwork/tests/test_mboxviews.py b/patchwork/tests/test_mboxviews.py
index eadfd81c8e08..3ee83dc2d2ac 100644
--- a/patchwork/tests/test_mboxviews.py
+++ b/patchwork/tests/test_mboxviews.py
@@ -38,7 +38,9 @@ class MboxPatchResponseTest(TestCase):
             submission=patch,
             submitter=self.person,
             content='comment 2 text\nAcked-by: 2\n')
-        response = self.client.get(reverse('patch-mbox', args=[patch.id]))
+        response = self.client.get(
+            reverse('patch-mbox', args=[self.project.linkname,
+                                        patch.url_msgid]))
         self.assertContains(response, 'Acked-by: 1\nAcked-by: 2\n')
 
     def test_patch_utf8_nbsp(self):
@@ -50,7 +52,9 @@ class MboxPatchResponseTest(TestCase):
             submission=patch,
             submitter=self.person,
             content=u'comment\nAcked-by:\u00A0 foo')
-        response = self.client.get(reverse('patch-mbox', args=[patch.id]))
+        response = self.client.get(
+            reverse('patch-mbox', args=[self.project.linkname,
+                                        patch.url_msgid]))
         self.assertContains(response, u'\u00A0 foo\n')
 
 
@@ -60,10 +64,10 @@ class MboxPatchSplitResponseTest(TestCase):
        and places it before an '---' update line."""
 
     def setUp(self):
-        project = create_project()
+        self.project = create_project()
         self.person = create_person()
         self.patch = create_patch(
-            project=project,
+            project=self.project,
             submitter=self.person,
             diff='',
             content='comment 1 text\nAcked-by: 1\n---\nupdate\n')
@@ -73,7 +77,9 @@ class MboxPatchSplitResponseTest(TestCase):
             content='comment 2 text\nAcked-by: 2\n')
 
     def test_patch_response(self):
-        response = self.client.get(reverse('patch-mbox', args=[self.patch.id]))
+        response = self.client.get(
+            reverse('patch-mbox', args=[self.project.linkname,
+                                        self.patch.url_msgid]))
         self.assertContains(response, 'Acked-by: 1\nAcked-by: 2\n')
 
 
@@ -83,7 +89,9 @@ class MboxHeaderTest(TestCase):
 
     def _test_header_passthrough(self, header):
         patch = create_patch(headers=header + '\n')
-        response = self.client.get(reverse('patch-mbox', args=[patch.id]))
+        response = self.client.get(
+            reverse('patch-mbox', args=[patch.project.linkname,
+                                        patch.url_msgid]))
         self.assertContains(response, header)
 
     def test_header_passthrough_cc(self):
@@ -114,14 +122,18 @@ class MboxHeaderTest(TestCase):
     def test_patchwork_id_header(self):
         """Validate inclusion of generated 'X-Patchwork-Id' header."""
         patch = create_patch()
-        response = self.client.get(reverse('patch-mbox', args=[patch.id]))
+        response = self.client.get(
+            reverse('patch-mbox', args=[patch.project.linkname,
+                                        patch.url_msgid]))
         self.assertContains(response, 'X-Patchwork-Id: %d' % patch.id)
 
     def test_patchwork_delegate_header(self):
         """Validate inclusion of generated 'X-Patchwork-Delegate' header."""
         user = create_user()
         patch = create_patch(delegate=user)
-        response = self.client.get(reverse('patch-mbox', args=[patch.id]))
+        response = self.client.get(
+            reverse('patch-mbox', args=[patch.project.linkname,
+                                        patch.url_msgid]))
         self.assertContains(response, 'X-Patchwork-Delegate: %s' % user.email)
 
     def test_patchwork_from_header(self):
@@ -131,7 +143,9 @@ class MboxHeaderTest(TestCase):
 
         person = create_person(name='Jonathon Doe', email=email)
         patch = create_patch(submitter=person, headers=from_header)
-        response = self.client.get(reverse('patch-mbox', args=[patch.id]))
+        response = self.client.get(
+            reverse('patch-mbox', args=[patch.project.linkname,
+                                        patch.url_msgid]))
         self.assertContains(response, from_header)
         self.assertContains(response, 'X-Patchwork-Submitter: %s <%s>' % (
             person.name, email))
@@ -147,12 +161,16 @@ class MboxHeaderTest(TestCase):
         person = create_person(name=u'©ool guŷ')
         patch = create_patch(submitter=person)
         from_email = '<' + person.email + '>'
-        response = self.client.get(reverse('patch-mbox', args=[patch.id]))
+        response = self.client.get(
+            reverse('patch-mbox', args=[patch.project.linkname,
+                                        patch.url_msgid]))
         self.assertContains(response, from_email)
 
     def test_date_header(self):
         patch = create_patch()
-        response = self.client.get(reverse('patch-mbox', args=[patch.id]))
+        response = self.client.get(
+            reverse('patch-mbox', args=[patch.project.linkname,
+                                        patch.url_msgid]))
         mail = email.message_from_string(response.content.decode())
         mail_date = dateutil.parser.parse(mail['Date'])
         # patch dates are all in UTC
@@ -170,7 +188,9 @@ class MboxHeaderTest(TestCase):
         patch.headers = 'Date: %s\n' % date.strftime("%a, %d %b %Y %T %z")
         patch.save()
 
-        response = self.client.get(reverse('patch-mbox', args=[patch.id]))
+        response = self.client.get(
+            reverse('patch-mbox', args=[patch.project.linkname,
+                                        patch.url_msgid]))
         mail = email.message_from_string(response.content.decode())
         mail_date = dateutil.parser.parse(mail['Date'])
         self.assertEqual(mail_date, date)
@@ -187,9 +207,11 @@ class MboxCommentPostcriptUnchangedTest(TestCase):
         before.
         """
         content = 'some comment\n---\n some/file | 1 +\n'
-        patch = create_patch(content=content, diff='')
+        project = create_project()
+        patch = create_patch(content=content, diff='', project=project)
 
-        response = self.client.get(reverse('patch-mbox', args=[patch.id]))
+        response = self.client.get(
+            reverse('patch-mbox', args=[project.linkname, patch.url_msgid]))
 
         self.assertContains(response, content)
         self.assertNotContains(response, content + '\n')
@@ -202,7 +224,8 @@ class MboxSeriesDependencies(TestCase):
         patch_b = create_series_patch(series=patch_a.series)
 
         response = self.client.get('%s?series=*' % reverse(
-            'patch-mbox', args=[patch_b.patch.id]))
+            'patch-mbox', args=[patch_b.patch.project.linkname,
+                                patch_b.patch.url_msgid]))
 
         self.assertContains(response, patch_a.patch.content)
         self.assertContains(response, patch_b.patch.content)
@@ -213,6 +236,6 @@ class MboxSeriesDependencies(TestCase):
         patch = create_patch()
 
         response = self.client.get('%s?series=*' % reverse(
-            'patch-mbox', args=[patch.id]))
+            'patch-mbox', args=[patch.project.linkname, patch.url_msgid]))
 
         self.assertEqual(response.status_code, 404)
diff --git a/patchwork/urls.py b/patchwork/urls.py
index 935e25fac6ac..e315d87251c7 100644
--- a/patchwork/urls.py
+++ b/patchwork/urls.py
@@ -38,22 +38,34 @@ urlpatterns = [
         name='project-detail'),
 
     # patch views
-    url(r'^patch/(?P<patch_id>\d+)/$', patch_views.patch_detail,
-        name='patch-detail'),
-    url(r'^patch/(?P<patch_id>\d+)/raw/$', patch_views.patch_raw,
-        name='patch-raw'),
-    url(r'^patch/(?P<patch_id>\d+)/mbox/$', patch_views.patch_mbox,
-        name='patch-mbox'),
+    url(r'^project/(?P<project_id>[^/]+)/patch/(?P<msgid>[^/]+)/$',
+        patch_views.patch_detail, name='patch-detail'),
+    url(r'^project/(?P<project_id>[^/]+)/patch/(?P<msgid>[^/]+)/raw/$',
+        patch_views.patch_raw, name='patch-raw'),
+    url(r'^project/(?P<project_id>[^/]+)/patch/(?P<msgid>[^/]+)/mbox/$',
+        patch_views.patch_mbox, name='patch-mbox'),
+    # ... old-style /patch/N/* urls
+    url(r'^patch/(?P<patch_id>\d+)(?P<target>.*)/$', patch_views.patch_by_id,
+        name='patch-id-redirect'),
 
     # cover views
-    url(r'^cover/(?P<cover_id>\d+)/$', cover_views.cover_detail,
-        name='cover-detail'),
-    url(r'^cover/(?P<cover_id>\d+)/mbox/$', cover_views.cover_mbox,
-        name='cover-mbox'),
+    url(r'^project/(?P<project_id>[^/]+)/cover/(?P<msgid>[^/]+)/$',
+        cover_views.cover_detail, name='cover-detail'),
+    url(r'^project/(?P<project_id>[^/]+)/cover/(?P<msgid>[^/]+)/mbox/$',
+        cover_views.cover_mbox, name='cover-mbox'),
+    # ... old-style /cover/N/* urls
+    url(r'^cover/(?P<cover_id>\d+)(?P<target>.*)/$', cover_views.cover_by_id,
+        name='cover-id-redirect'),
 
     # comment views
     url(r'^comment/(?P<comment_id>\d+)/$', comment_views.comment,
         name='comment-redirect'),
+    url(r'^project/(?P<project_id>[^/]+)/comment/(?P<msgid>[^/]+)/$',
+        comment_views.comment_by_msgid, name='comment-msgid-redirect'),
+
+    # Patch/cover/comment by msgid only, guess project
+    url(r'^message/(?P<msgid>[^/]+)$', patch_views.patch_by_msgid,
+        name='msgid-redirect'),
 
     # series views
     url(r'^series/(?P<series_id>\d+)/mbox/$', series_views.series_mbox,
diff --git a/patchwork/views/__init__.py b/patchwork/views/__init__.py
index 0c64c93e976e..d66b8830f075 100644
--- a/patchwork/views/__init__.py
+++ b/patchwork/views/__init__.py
@@ -276,7 +276,7 @@ def generic_list(request, project, view, view_args=None, filter_settings=None,
     patches = patches.select_related('state', 'submitter', 'delegate')
 
     patches = patches.only('state', 'submitter', 'delegate', 'project',
-                           'name', 'date')
+                           'name', 'date', 'msgid')
 
     # we also need checks and series
     patches = patches.prefetch_related(
diff --git a/patchwork/views/comment.py b/patchwork/views/comment.py
index 4aa924b969e0..37358c033de3 100644
--- a/patchwork/views/comment.py
+++ b/patchwork/views/comment.py
@@ -15,10 +15,27 @@ def comment(request, comment_id):
                                              id=comment_id).submission
     if models.Patch.objects.filter(id=submission.id).exists():
         url = 'patch-detail'
-        key = 'patch_id'
     else:
         url = 'cover-detail'
-        key = 'cover_id'
 
     return http.HttpResponseRedirect('%s#%s' % (
-        reverse(url, kwargs={key: submission.id}), comment_id))
+        reverse(url, kwargs={'project_id': submission.project.linkname,
+                             'msgid': submission.url_msgid}), comment_id))
+
+
+def comment_by_msgid(request, project_id, msgid):
+    db_msgid = ('<%s>' % msgid)
+    project = shortcuts.get_object_or_404(models.Project, linkname=project_id)
+    comment = shortcuts.get_object_or_404(
+        models.Comment,
+        submission__project_id=project.id,
+        msgid=db_msgid)
+    if models.Patch.objects.filter(id=comment.submission.id).exists():
+        url = 'patch-detail'
+    else:
+        url = 'cover-detail'
+
+    return http.HttpResponseRedirect('%s#%s' % (
+        reverse(url, kwargs={'project_id': project.linkname,
+                             'msgid': comment.submission.url_msgid}),
+        comment.id))
diff --git a/patchwork/views/cover.py b/patchwork/views/cover.py
index cb8fd3cab64b..9b0627892608 100644
--- a/patchwork/views/cover.py
+++ b/patchwork/views/cover.py
@@ -11,19 +11,27 @@ from django.shortcuts import render
 from django.urls import reverse
 
 from patchwork.models import CoverLetter
+from patchwork.models import Project
 from patchwork.models import Submission
 from patchwork.views.utils import cover_to_mbox
 
 
-def cover_detail(request, cover_id):
+def cover_detail(request, project_id, msgid):
+    project = get_object_or_404(Project, linkname=project_id)
+    db_msgid = ('<%s>' % msgid)
+
     # redirect to patches where necessary
     try:
-        cover = get_object_or_404(CoverLetter, id=cover_id)
+        cover = get_object_or_404(CoverLetter, project_id=project.id,
+                                  msgid=db_msgid)
     except Http404 as exc:
-        submissions = Submission.objects.filter(id=cover_id)
+        submissions = Submission.objects.filter(project_id=project.id,
+                                                msgid=db_msgid)
         if submissions:
             return HttpResponseRedirect(
-                reverse('patch-detail', kwargs={'patch_id': cover_id}))
+                reverse('patch-detail',
+                        kwargs={'project_id': project.linkname,
+                                'msgid': msgid}))
         raise exc
 
     context = {
@@ -41,8 +49,11 @@ def cover_detail(request, cover_id):
     return render(request, 'patchwork/submission.html', context)
 
 
-def cover_mbox(request, cover_id):
-    cover = get_object_or_404(CoverLetter, id=cover_id)
+def cover_mbox(request, project_id, msgid):
+    db_msgid = ('<%s>' % msgid)
+    project = get_object_or_404(Project, linkname=project_id)
+    cover = get_object_or_404(CoverLetter, project_id=project.id,
+                              msgid=db_msgid)
 
     response = HttpResponse(content_type='text/plain')
     response.write(cover_to_mbox(cover))
@@ -50,3 +61,18 @@ def cover_mbox(request, cover_id):
         cover.filename)
 
     return response
+
+
+def cover_by_id(request, cover_id, target):
+    cover = get_object_or_404(CoverLetter, id=cover_id)
+
+    url = reverse('cover-detail', kwargs={'project_id': cover.project.linkname,
+                                          'msgid': cover.url_msgid})
+
+    if target:
+        if target[0] == '/':
+            # strip the leading slash as we get a slash from the reverse()
+            target = target[1:]
+        url += target + '/'
+
+    return HttpResponseRedirect(url)
diff --git a/patchwork/views/patch.py b/patchwork/views/patch.py
index 862dc83dfe79..55272ab9ba09 100644
--- a/patchwork/views/patch.py
+++ b/patchwork/views/patch.py
@@ -14,6 +14,7 @@ from django.urls import reverse
 
 from patchwork.forms import CreateBundleForm
 from patchwork.forms import PatchForm
+from patchwork.models import Comment
 from patchwork.models import Bundle
 from patchwork.models import Patch
 from patchwork.models import Project
@@ -34,15 +35,21 @@ def patch_list(request, project_id):
     return render(request, 'patchwork/list.html', context)
 
 
-def patch_detail(request, patch_id):
+def patch_detail(request, project_id, msgid):
+    project = get_object_or_404(Project, linkname=project_id)
+    db_msgid = ('<%s>' % msgid)
+
     # redirect to cover letters where necessary
     try:
-        patch = get_object_or_404(Patch, id=patch_id)
-    except Http404 as exc:
-        submissions = Submission.objects.filter(id=patch_id)
+        patch = Patch.objects.get(project_id=project.id, msgid=db_msgid)
+    except Patch.DoesNotExist as exc:
+        submissions = Submission.objects.filter(project_id=project.id,
+                                                msgid=db_msgid)
         if submissions:
             return HttpResponseRedirect(
-                reverse('cover-detail', kwargs={'cover_id': patch_id}))
+                reverse('cover-detail',
+                        kwargs={'project_id': project.linkname,
+                                'msgid': msgid}))
         raise exc
 
     editable = patch.is_editable(request.user)
@@ -64,7 +71,7 @@ def patch_detail(request, patch_id):
             action = action.lower()
 
         if action == 'createbundle':
-            bundle = Bundle(owner=request.user, project=patch.project)
+            bundle = Bundle(owner=request.user, project=project)
             createbundleform = CreateBundleForm(instance=bundle,
                                                 data=request.POST)
             if createbundleform.is_valid():
@@ -115,8 +122,10 @@ def patch_detail(request, patch_id):
     return render(request, 'patchwork/submission.html', context)
 
 
-def patch_raw(request, patch_id):
-    patch = get_object_or_404(Patch, id=patch_id)
+def patch_raw(request, project_id, msgid):
+    db_msgid = ('<%s>' % msgid)
+    project = get_object_or_404(Project, linkname=project_id)
+    patch = get_object_or_404(Patch, project_id=project.id, msgid=db_msgid)
 
     response = HttpResponse(content_type="text/x-patch")
     response.write(patch.diff)
@@ -126,8 +135,10 @@ def patch_raw(request, patch_id):
     return response
 
 
-def patch_mbox(request, patch_id):
-    patch = get_object_or_404(Patch, id=patch_id)
+def patch_mbox(request, project_id, msgid):
+    db_msgid = ('<%s>' % msgid)
+    project = get_object_or_404(Project, linkname=project_id)
+    patch = get_object_or_404(Patch, project_id=project.id, msgid=db_msgid)
     series_id = request.GET.get('series')
 
     response = HttpResponse(content_type='text/plain')
@@ -144,3 +155,45 @@ def patch_mbox(request, patch_id):
         patch.filename)
 
     return response
+
+
+def patch_by_id(request, patch_id, target):
+    patch = get_object_or_404(Patch, id=patch_id)
+
+    url = reverse('patch-detail', kwargs={'project_id': patch.project.linkname,
+                                          'msgid': patch.url_msgid})
+
+    if target:
+        if target[0] == '/':
+            # strip the leading slash as we get a slash from the reverse()
+            target = target[1:]
+        url += target + '/'
+
+    return HttpResponseRedirect(url)
+
+
+def patch_by_msgid(request, msgid):
+    db_msgid = ('<%s>' % msgid)
+
+    patches = Patch.objects.filter(msgid=db_msgid)
+    if patches:
+        patch = patches.first()
+        return HttpResponseRedirect(
+            reverse('patch-detail',
+                    kwargs={'project_id': patch.project.linkname,
+                            'msgid': patch.url_msgid}))
+
+    subs = Submission.objects.filter(msgid=db_msgid)
+    if subs:
+        cover = subs.first()
+        return HttpResponseRedirect(
+            reverse('cover-detail',
+                    kwargs={'project_id': cover.project.linkname,
+                            'msgid': cover.url_msgid}))
+
+    comments = Comment.objects.filter(msgid=db_msgid)
+    if comments:
+        return HttpResponseRedirect(comments.first().get_absolute_url())
+
+    raise Http404("No patch, cover letter of comment matching %s found."
+                  % msgid)
diff --git a/releasenotes/notes/new-url-schema-f1c799b5eb078ea4.yaml b/releasenotes/notes/new-url-schema-f1c799b5eb078ea4.yaml
new file mode 100644
index 000000000000..9356d671b3f7
--- /dev/null
+++ b/releasenotes/notes/new-url-schema-f1c799b5eb078ea4.yaml
@@ -0,0 +1,10 @@
+---
+features:
+  - |
+    The URL schema now uses message IDs, rather than patch IDs, by
+    default. Old URLs will redirect to the new URLs.
+  - |
+    A new ``/message/aaa@bbb.ccc/`` URL has been added, which will
+    look up a message by ID. If it exists as a patch, cover letter or
+    comment in any project, it will redirect to that. If it exists in
+    multiple projects, the project selection is arbitrary.
