diff --git a/patchwork/models.py b/patchwork/models.py
index 32d1b3c2adc5..ccb3b0acb372 100644
--- a/patchwork/models.py
+++ b/patchwork/models.py
@@ -335,6 +335,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,
@@ -400,10 +406,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
@@ -581,10 +591,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
diff --git a/patchwork/templates/patchwork/partials/download-buttons.html b/patchwork/templates/patchwork/partials/download-buttons.html
index 21933bd28bcb..e75a25cee5a9 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 2d090d98d619..985e9bee05a0 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 e79dd92497a4..ad452dd8f7b7 100644
--- a/patchwork/templates/patchwork/submission.html
+++ b/patchwork/templates/patchwork/submission.html
@@ -91,7 +91,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 %}
@@ -103,7 +103,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 18408ecb95f6..32fbfaf72181 100644
--- a/patchwork/tests/test_detail.py
+++ b/patchwork/tests/test_detail.py
@@ -14,10 +14,38 @@ from patchwork.tests.utils import create_patch
 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-id-redirect',
+                                kwargs={'cover_id': cover.id})
+        redirect_url = reverse('cover-detail',
+                               kwargs={'project_id': cover.project.linkname,
+                                       'msgid': cover.url_msgid})
 
-        requested_url = reverse('cover-detail', kwargs={'cover_id': patch_id})
-        redirect_url = reverse('patch-detail', kwargs={'patch_id': patch_id})
+        response = self.client.get(requested_url)
+        self.assertRedirects(response, redirect_url)
+
+    def test_old_mbox_url(self):
+        cover = create_cover()
+
+        requested_url = reverse('cover-mbox-redirect',
+                                kwargs={'cover_id': cover.id})
+        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)
@@ -26,10 +54,50 @@ class CoverLetterViewTest(TestCase):
 class PatchViewTest(TestCase):
 
     def test_redirect(self):
-        cover_id = create_cover().id
+        cover = create_cover()
+
+        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)
+
+    def test_old_detail_url(self):
+        patch = create_patch()
+
+        requested_url = reverse('patch-id-redirect',
+                                kwargs={'patch_id': patch.id})
+        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-mbox-redirect',
+                                kwargs={'patch_id': patch.id})
+        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-detail', kwargs={'patch_id': cover_id})
-        redirect_url = reverse('cover-detail', kwargs={'cover_id': cover_id})
+        requested_url = reverse('patch-raw-redirect',
+                                kwargs={'patch_id': patch.id})
+        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)
@@ -43,24 +111,28 @@ class PatchViewTest(TestCase):
         patch.commit_ref = unescaped_string
         patch.pull_url = unescaped_string
         patch.name = unescaped_string
-        patch.msgid = unescaped_string
+        patch.msgid = '<' + unescaped_string + '>'
         patch.headers = unescaped_string
         patch.content = unescaped_string
         patch.save()
-        requested_url = reverse('patch-detail', kwargs={'patch_id': patch.id})
+        requested_url = reverse('patch-detail',
+                                kwargs={'project_id': patch.project.linkname,
+                                        'msgid': patch.url_msgid})
         response = self.client.get(requested_url)
         self.assertNotIn('<b>TEST</b>'.encode('utf-8'), response.content)
 
 
 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)
@@ -68,8 +140,8 @@ class CommentRedirectTest(TestCase):
 
     def test_patch_redirect(self):
         patch = create_patch()
-        self._test_redirect(patch, 'patch-detail', 'patch_id')
+        self._test_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')
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 3de5e8375f1e..3854a856c4db 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):
@@ -113,7 +121,9 @@ class MboxHeaderTest(TestCase):
 
     def _test_header_dropped(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.assertNotContains(response, header)
 
     def test_header_dropped_content_transfer_encoding(self):
@@ -129,14 +139,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):
@@ -146,7 +160,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))
@@ -162,12 +178,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
@@ -185,7 +205,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)
@@ -202,9 +224,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')
@@ -224,7 +248,8 @@ class MboxSeriesDependencies(TestCase):
         _, patch_a, patch_b = self._create_patches()
 
         response = self.client.get('%s?series=*' % reverse(
-            'patch-mbox', args=[patch_b.id]))
+            'patch-mbox', args=[patch_b.patch.project.linkname,
+                                patch_b.patch.url_msgid]))
 
         self.assertContains(response, patch_a.content)
         self.assertContains(response, patch_b.content)
@@ -233,7 +258,9 @@ class MboxSeriesDependencies(TestCase):
         series, patch_a, patch_b = self._create_patches()
 
         response = self.client.get('%s?series=%d' % (
-            reverse('patch-mbox', args=[patch_b.id]), series.id))
+            reverse('patch-mbox', args=[patch_b.patch.project.linkname,
+                                        patch_b.patch.url_msgid]),
+            series.id))
 
         self.assertContains(response, patch_a.content)
         self.assertContains(response, patch_b.content)
@@ -243,7 +270,8 @@ class MboxSeriesDependencies(TestCase):
 
         for value in ('foo', str(series.id + 1)):
             response = self.client.get('%s?series=%s' % (
-                reverse('patch-mbox', args=[patch_b.patch.id]), value))
+                reverse('patch-mbox', args=[patch_b.patch.project.linkname,
+                                            patch_b.patch.url_msgid]), value))
 
             self.assertEqual(response.status_code, 404)
 
@@ -253,7 +281,7 @@ class MboxSeriesDependencies(TestCase):
         patch = create_patch(series=None)
 
         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 c24bf55ee83f..dcdcfb49e67e 100644
--- a/patchwork/urls.py
+++ b/patchwork/urls.py
@@ -38,18 +38,41 @@ 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'),
+    # NOTE(dja): Per the RFC, msgids can contain slashes. There doesn't seem
+    # to be an easy way to tell Django to urlencode the slash when generating
+    # URLs, so instead we must use a permissive regex (.+ rather than [^/]+).
+    # This also means we need to put the raw and mbox URLs first, otherwise the
+    # patch-detail regex will just greedily grab those parts into a massive and
+    # wrong msgid.
+    #
+    # This does mean that message-ids that end in '/raw/' or '/mbox/' will not
+    # work, but it is RECOMMENDED by the RFC that the right hand side of the @
+    # contains a domain, so I think breaking on messages that have "domains"
+    # ending in /raw/ or /mbox/ is good enough.
+    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'),
+    url(r'^project/(?P<project_id>[^/]+)/patch/(?P<msgid>.+)/$',
+        patch_views.patch_detail, name='patch-detail'),
+    # ... old-style /patch/N/* urls
+    url(r'^patch/(?P<patch_id>\d+)/raw/$', patch_views.patch_raw_by_id,
+        name='patch-raw-redirect'),
+    url(r'^patch/(?P<patch_id>\d+)/mbox/$', patch_views.patch_mbox_by_id,
+        name='patch-mbox-redirect'),
+    url(r'^patch/(?P<patch_id>\d+)/$', 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>.+)/mbox/$',
+        cover_views.cover_mbox, name='cover-mbox'),
+    url(r'^project/(?P<project_id>[^/]+)/cover/(?P<msgid>.+)/$',
+        cover_views.cover_detail, name='cover-detail'),
+    # ... old-style /cover/N/* urls
+    url(r'^cover/(?P<cover_id>\d+)/mbox/$', cover_views.cover_mbox_by_id,
+        name='cover-mbox-redirect'),
+    url(r'^cover/(?P<cover_id>\d+)/$', cover_views.cover_by_id,
+        name='cover-id-redirect'),
 
     # comment views
     url(r'^comment/(?P<comment_id>\d+)/$', comment_views.comment,
diff --git a/patchwork/views/__init__.py b/patchwork/views/__init__.py
index 6ec53ddacbe9..ad17a0702deb 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,
                                      'series')
 
     patches = patches.only('state', 'submitter', 'delegate', 'project',
-                           'series__name', 'name', 'date')
+                           'series__name', '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..7dee8dc40c7e 100644
--- a/patchwork/views/comment.py
+++ b/patchwork/views/comment.py
@@ -15,10 +15,9 @@ 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))
diff --git a/patchwork/views/cover.py b/patchwork/views/cover.py
index 08b633a11f78..54962abb7682 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 = {
@@ -40,8 +48,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))
@@ -49,3 +60,21 @@ def cover_mbox(request, cover_id):
         cover.filename)
 
     return response
+
+
+def cover_by_id(request, cover_id):
+    cover = get_object_or_404(CoverLetter, id=cover_id)
+
+    url = reverse('cover-detail', kwargs={'project_id': cover.project.linkname,
+                                          'msgid': cover.url_msgid})
+
+    return HttpResponseRedirect(url)
+
+
+def cover_mbox_by_id(request, cover_id):
+    cover = get_object_or_404(CoverLetter, id=cover_id)
+
+    url = reverse('cover-mbox', kwargs={'project_id': cover.project.linkname,
+                                        'msgid': cover.url_msgid})
+
+    return HttpResponseRedirect(url)
diff --git a/patchwork/views/patch.py b/patchwork/views/patch.py
index 277b2816e31e..f34053ce57da 100644
--- a/patchwork/views/patch.py
+++ b/patchwork/views/patch.py
@@ -34,15 +34,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 +70,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():
@@ -114,8 +120,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)
@@ -125,8 +133,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')
@@ -143,3 +153,30 @@ def patch_mbox(request, patch_id):
         patch.filename)
 
     return response
+
+
+def patch_by_id(request, patch_id):
+    patch = get_object_or_404(Patch, id=patch_id)
+
+    url = reverse('patch-detail', kwargs={'project_id': patch.project.linkname,
+                                          'msgid': patch.url_msgid})
+
+    return HttpResponseRedirect(url)
+
+
+def patch_mbox_by_id(request, patch_id):
+    patch = get_object_or_404(Patch, id=patch_id)
+
+    url = reverse('patch-mbox', kwargs={'project_id': patch.project.linkname,
+                                        'msgid': patch.url_msgid})
+
+    return HttpResponseRedirect(url)
+
+
+def patch_raw_by_id(request, patch_id):
+    patch = get_object_or_404(Patch, id=patch_id)
+
+    url = reverse('patch-raw', kwargs={'project_id': patch.project.linkname,
+                                       'msgid': patch.url_msgid})
+
+    return HttpResponseRedirect(url)
diff --git a/releasenotes/notes/new-url-schema-f1c799b5eb078ea4.yaml b/releasenotes/notes/new-url-schema-f1c799b5eb078ea4.yaml
new file mode 100644
index 000000000000..288944420082
--- /dev/null
+++ b/releasenotes/notes/new-url-schema-f1c799b5eb078ea4.yaml
@@ -0,0 +1,5 @@
+---
+features:
+  - |
+    The URL schema now uses message IDs, rather than patch IDs, by
+    default. Old URLs will redirect to the new URLs.
