diff --git a/elfutils.spec b/elfutils.spec
index ebbfa96..d0eb699 100644
--- a/elfutils.spec
+++ b/elfutils.spec
@@ -1,6 +1,6 @@
 Name: elfutils
 Version: 0.186
-%global baserelease 3
+%global baserelease 4
 Release: %{baserelease}%{?dist}
 URL: http://elfutils.org/
 %global source_url ftp://sourceware.org/pub/elfutils/%{version}/
@@ -183,6 +183,8 @@ License: GPLv3+ and (GPLv2+ or LGPLv3+)
 %if 0%{!?_isa:1}
 Provides: elfutils-debuginfod-client%{depsuffix} = %{version}-%{release}
 %endif
+# For debuginfod-find binary
+Requires: elfutils-libs%{depsuffix} = %{version}-%{release}
 %if 0%{?rhel} >= 8 || 0%{?fedora} >= 20
 # Instead of the weak forward dependency from -libs to -debuginfod-client,
 # we'll add weak reverse dependencies from some of the many programs that
@@ -418,6 +420,10 @@ exit 0
 %systemd_postun_with_restart debuginfod.service
 
 %changelog
+* Fri Apr  8 2022 Mark Wielaard <mjw@redhat.com> - 0.186-4
+- Add an explicit versioned requires from elfutils-debuginfod-client
+  on elfutils-libs.
+
 * Tue Mar 22 2022 Mark Wielaard <mjw@redhat.com> - 0.186-3
 - Remove brew testsuite workarounds