diff --git a/0001-hif-Match-unavailable-packages-for-the-what-provides.patch b/0001-hif-Match-unavailable-packages-for-the-what-provides.patch
new file mode 100644
index 0000000..0c2a474
--- /dev/null
+++ b/0001-hif-Match-unavailable-packages-for-the-what-provides.patch
@@ -0,0 +1,24 @@
+From 062aec45763534f9d57aaee2e2915dcdeb3d25c7 Mon Sep 17 00:00:00 2001
+From: Kalev Lember <klember@redhat.com>
+Date: Thu, 2 Jun 2016 14:01:43 +0200
+Subject: [PATCH] hif: Match unavailable packages for the what-provides query
+
+---
+ backends/hif/pk-backend-hif.c | 1 +
+ 1 file changed, 1 insertion(+)
+
+diff --git a/backends/hif/pk-backend-hif.c b/backends/hif/pk-backend-hif.c
+index 4f0d633..0f644f6 100644
+--- a/backends/hif/pk-backend-hif.c
++++ b/backends/hif/pk-backend-hif.c
+@@ -636,6 +636,7 @@ hif_utils_create_sack_for_filters (PkBackendJob *job,
+ 	case PK_ROLE_ENUM_SEARCH_DETAILS:
+ 	case PK_ROLE_ENUM_SEARCH_FILE:
+ 	case PK_ROLE_ENUM_GET_DETAILS:
++	case PK_ROLE_ENUM_WHAT_PROVIDES:
+ 		flags |= HIF_SACK_ADD_FLAG_UNAVAILABLE;
+ 		break;
+ 	default:
+-- 
+2.5.5
+
diff --git a/PackageKit.spec b/PackageKit.spec
index afde45b..f5a496c 100644
--- a/PackageKit.spec
+++ b/PackageKit.spec
@@ -7,7 +7,7 @@
 Summary:   Package management service
 Name:      PackageKit
 Version:   1.1.1
-Release:   2%{?dist}
+Release:   3%{?dist}
 License:   GPLv2+ and LGPLv2+
 URL:       http://www.freedesktop.org/software/PackageKit/
 Source0:   http://www.freedesktop.org/software/PackageKit/releases/%{name}-%{version}.tar.xz
@@ -16,6 +16,7 @@ Source0:   http://www.freedesktop.org/software/PackageKit/releases/%{name}-%{ver
 Patch0:    PackageKit-0.3.8-Fedora-Vendor.conf.patch
 # Backported from upstream
 Patch1:    0001-Require-admin-authorisation-to-trigger-a-distro-upgr.patch
+Patch2:    0001-hif-Match-unavailable-packages-for-the-what-provides.patch
 
 Requires: %{name}-glib%{?_isa} = %{version}-%{release}
 Requires: shared-mime-info
@@ -150,6 +151,7 @@ using PackageKit.
 %setup -q
 %patch0 -p1 -b .fedora
 %patch1 -p1
+%patch2 -p1
 
 %build
 %configure \
@@ -277,6 +279,9 @@ systemctl disable packagekit-offline-update.service > /dev/null 2>&1 || :
 %{_datadir}/vala/vapi/packagekit-glib2.vapi
 
 %changelog
+* Tue Jun 07 2016 Kalev Lember <klember@redhat.com> - 1.1.1-3
+- Match unavailable packages for the what-provides query
+
 * Sat May 28 2016 Kalev Lember <klember@redhat.com> - 1.1.1-2
 - Require admin authorisation to trigger a distro upgrade (#1335458)