diff --git a/lib/gerrit.py b/lib/gerrit.py
index ea5fba9..042f0af 100644
--- a/lib/gerrit.py
+++ b/lib/gerrit.py
@@ -214,6 +214,10 @@
       # Use commit:sha1 for accurate query results (crbug.com/358381).
       kwargs['commit'] = change
       change = None
+    elif change and cros_patch.IsChangeID(change, strict=True):
+      # Use change:change-id for accurate query results (crbug.com/358758).
+      kwargs['change'] = change
+      change = None
 
     if change and query_kwds.get('change'):
       raise GerritException('Bad query params: provided a change-id-like query,'