diff --git a/pre-upload.py b/pre-upload.py
index db6edc2..441d873 100755
--- a/pre-upload.py
+++ b/pre-upload.py
@@ -100,7 +100,6 @@
 # excluded from presubmit checks. Lines beginning with '#' are ignored.
 _IGNORE_FILE = '.presubmitignore'
 
-
 # Exceptions
 
 
@@ -560,12 +559,21 @@
 
 def _check_change_has_valid_cq_depend(_project, commit):
   """Check for a correctly formatted Cq-Depend field in the commit message."""
+  desc = _get_commit_desc(commit)
   msg = 'Changelist has invalid Cq-Depend target.'
   example = 'Example: Cq-Depend: chromium:1234, chrome-internal:2345'
   try:
-    patch.GetPaladinDeps(_get_commit_desc(commit))
+    patch.GetPaladinDeps(desc)
   except ValueError as ex:
     return HookFailure(msg, [example, str(ex)])
+  # Check that Cq-Depend is in the same paragraph as Change-Id.
+  msg = 'Cq-Depend (or CQ-DEPEND) is not in the same paragraph as Change-Id.'
+  paragraphs = desc.split('\n\n')
+  for paragraph in paragraphs:
+    if (re.search(r'^Cq-Depend:', paragraph, re.M) or
+        re.search(r'^CQ-DEPEND=', paragraph, re.M)) \
+        and not re.search('^Change-Id:', paragraph, re.M):
+      return HookFailure(msg)
 
 
 def _check_change_is_contribution(_project, commit):
diff --git a/pre-upload_unittest.py b/pre-upload_unittest.py
index 7ad2504..99b695c 100755
--- a/pre-upload_unittest.py
+++ b/pre-upload_unittest.py
@@ -1053,12 +1053,13 @@
 
   def testNormal(self):
     """Accept valid Cq-Depends line."""
-    self.assertMessageAccepted('\nCq-Depend: chromium:1234\n')
+    self.assertMessageAccepted('\nCq-Depend: chromium:1234\nChange-Id: I123')
 
   def testInvalid(self):
     """Reject invalid Cq-Depends line."""
     self.assertMessageRejected('\nCq-Depend=chromium=1234\n')
     self.assertMessageRejected('\nCq-Depend: None\n')
+    self.assertMessageRejected('\nCq-Depend: chromium:1234\n\nChange-Id: I123')
 
 
 class CheckCommitMessageContribution(CommitMessageTestCase):