diff --git a/polygerrit-ui/app/elements/core/gr-main-header/gr-main-header_html.js b/polygerrit-ui/app/elements/core/gr-main-header/gr-main-header_html.js
index 2e64b3b..e50b408 100644
--- a/polygerrit-ui/app/elements/core/gr-main-header/gr-main-header_html.js
+++ b/polygerrit-ui/app/elements/core/gr-main-header/gr-main-header_html.js
@@ -199,6 +199,7 @@
       ></gr-endpoint-decorator>
       <gr-smart-search
         id="search"
+        label="Search for changes"
         search-query="{{searchQuery}}"
       ></gr-smart-search>
       <gr-endpoint-decorator
diff --git a/polygerrit-ui/app/elements/core/gr-search-bar/gr-search-bar.js b/polygerrit-ui/app/elements/core/gr-search-bar/gr-search-bar.js
index 02b4efd..39d00069 100644
--- a/polygerrit-ui/app/elements/core/gr-search-bar/gr-search-bar.js
+++ b/polygerrit-ui/app/elements/core/gr-search-bar/gr-search-bar.js
@@ -171,6 +171,14 @@
         type: Number,
         value: 1,
       },
+      /**
+       * Invisible label for input element. This label is exposed to
+       * screen readers by nested element
+       */
+      label: {
+        type: String,
+        value: '',
+      },
     };
   }
 
diff --git a/polygerrit-ui/app/elements/core/gr-search-bar/gr-search-bar_html.js b/polygerrit-ui/app/elements/core/gr-search-bar/gr-search-bar_html.js
index e26f8a3..b0ef7af 100644
--- a/polygerrit-ui/app/elements/core/gr-search-bar/gr-search-bar_html.js
+++ b/polygerrit-ui/app/elements/core/gr-search-bar/gr-search-bar_html.js
@@ -30,6 +30,7 @@
   </style>
   <form>
     <gr-autocomplete
+      label="[[label]]"
       show-search-icon=""
       id="searchInput"
       text="{{_inputVal}}"
diff --git a/polygerrit-ui/app/elements/core/gr-smart-search/gr-smart-search.js b/polygerrit-ui/app/elements/core/gr-smart-search/gr-smart-search.js
index f6221c8..2d1212b 100644
--- a/polygerrit-ui/app/elements/core/gr-smart-search/gr-smart-search.js
+++ b/polygerrit-ui/app/elements/core/gr-smart-search/gr-smart-search.js
@@ -62,6 +62,14 @@
           return this._fetchAccounts.bind(this);
         },
       },
+      /**
+       * Invisible label for input element. This label is exposed to
+       * screen readers by nested element
+       */
+      label: {
+        type: String,
+        value: '',
+      },
     };
   }
 
diff --git a/polygerrit-ui/app/elements/core/gr-smart-search/gr-smart-search_html.js b/polygerrit-ui/app/elements/core/gr-smart-search/gr-smart-search_html.js
index bb741ce..d490308 100644
--- a/polygerrit-ui/app/elements/core/gr-smart-search/gr-smart-search_html.js
+++ b/polygerrit-ui/app/elements/core/gr-smart-search/gr-smart-search_html.js
@@ -20,6 +20,7 @@
   <style include="shared-styles"></style>
   <gr-search-bar
     id="search"
+    label="[[label]]"
     value="{{searchQuery}}"
     on-handle-search="_handleSearch"
     project-suggestions="[[_projectSuggestions]]"
diff --git a/polygerrit-ui/app/elements/gr-app-element_html.js b/polygerrit-ui/app/elements/gr-app-element_html.js
index ad47d52..47139ce 100644
--- a/polygerrit-ui/app/elements/gr-app-element_html.js
+++ b/polygerrit-ui/app/elements/gr-app-element_html.js
@@ -111,6 +111,7 @@
   <main>
     <gr-smart-search
       id="search"
+      label="Search for changes"
       search-query="{{params.query}}"
       hidden="[[!mobileSearch]]"
     >
diff --git a/polygerrit-ui/app/elements/shared/gr-autocomplete/gr-autocomplete.js b/polygerrit-ui/app/elements/shared/gr-autocomplete/gr-autocomplete.js
index e6a809e..4cf56a7 100644
--- a/polygerrit-ui/app/elements/shared/gr-autocomplete/gr-autocomplete.js
+++ b/polygerrit-ui/app/elements/shared/gr-autocomplete/gr-autocomplete.js
@@ -184,6 +184,14 @@
         type: Boolean,
         value: false,
       },
+      /**
+       * Invisible label for input element. This label is exposed to
+       * screen readers by paper-input
+       */
+      label: {
+        type: String,
+        value: '',
+      },
 
       /** The DOM element of the selected suggestion. */
       _selected: Object,
diff --git a/polygerrit-ui/app/elements/shared/gr-autocomplete/gr-autocomplete_html.js b/polygerrit-ui/app/elements/shared/gr-autocomplete/gr-autocomplete_html.js
index eae8741..c0e8abf 100644
--- a/polygerrit-ui/app/elements/shared/gr-autocomplete/gr-autocomplete_html.js
+++ b/polygerrit-ui/app/elements/shared/gr-autocomplete/gr-autocomplete_html.js
@@ -66,6 +66,12 @@
         height: 0;
         display: none;
       }
+      /* Hide label for input. The label is still visible for
+      screen readers. Workaround found at:
+      https://github.com/PolymerElements/paper-input/issues/478 */
+      --paper-input-container-label: {
+        display: none;
+      }
     }
     paper-input.warnUncommitted {
       --paper-input-container-input: {
@@ -85,6 +91,7 @@
     on-focus="_onInputFocus"
     on-blur="_onInputBlur"
     autocomplete="off"
+    label="[[label]]"
   >
     <!-- prefix as attribute is required to for polymer 1 -->
     <div slot="prefix" prefix="">