diff --git a/Makefile.selinux b/Makefile.selinux
new file mode 100644
index 0000000..b553c06
--- /dev/null
+++ b/Makefile.selinux
@@ -0,0 +1,16 @@
+TARGETS ?= rpm_hs
+SHARE ?= /usr/share
+MODULES ?= ${TARGETS:=.pp.bz2}
+
+all: ${TARGETS:=.pp.bz2}
+
+%.pp.bz2: %.pp
+	@echo Compressing $^ -\ $@
+	bzip2 -9 $^
+
+%.pp: %.te
+	make -f ${SHARE}/selinux/devel/Makefile $@
+
+clean:
+	rm -f *~ *.tc *.pp *.pp.bz2
+	rm -rf tmp
diff --git a/rpm.spec b/rpm.spec
index 612be83..5dfc178 100644
--- a/rpm.spec
+++ b/rpm.spec
@@ -70,6 +70,11 @@ Source10: rpmdb-rebuild.service
 Source20: rpmdb-migrate.service
 Source21: rpmdb_migrate
 
+# Needed for selinux subpackage
+Source100: Makefile.selinux
+Source101: rpm_hs.te
+Source102: rpm_hs.fc
+
 # Set rpmdb path to /usr/lib/sysimage/rpm
 Patch0: rpm-4.16.x-rpm_dbpath.patch
 # Disable autoconf config.site processing (#962837)
@@ -247,6 +252,9 @@ Requires(pre): coreutils
 Requires(pre): findutils
 Requires(pre): sed
 
+# Force the SELinux module to be installed if SELinux policy is installed
+Requires:      (%{name}-selinux = %{version}-%{release} if selinux-policy)
+
 %description
 The RPM Package Manager (RPM) is a powerful command line driven
 package management system capable of installing, uninstalling,
@@ -449,6 +457,24 @@ Adds measure support
 # with plugins
 %endif
 
+%package selinux
+Summary:        SELinux module for rpm
+BuildArch:      noarch
+BuildRequires:  bzip2
+BuildRequires:  make
+BuildRequires:  selinux-policy
+BuildRequires:  selinux-policy-devel
+Requires(post): selinux-policy-base >= %{_selinux_policy_version}
+Requires(post): policycoreutils
+Requires(post): policycoreutils-python-utils
+Requires(pre):  libselinux-utils
+Requires(post): libselinux-utils
+
+%description selinux
+This package provides the SELinux policy module to ensure rpm
+runs properly under an environment with SELinux enabled.
+
+
 %prep
 %autosetup -n rpm-%{srcver} %{?with_int_bdb:-a 1} -p1
 
@@ -461,6 +487,10 @@ ln -s db-%{bdbver} db
 sed -i -e "/_db_backend/ s/ bdb/ sqlite/g" macros.in
 %endif
 
+# SELinux policy files
+mkdir selinux-policy
+cp %{SOURCE100} %{SOURCE101} %{SOURCE102} selinux-policy
+
 %build
 %set_build_flags
 
@@ -506,6 +536,10 @@ pushd python
 %py3_build
 popd
 
+pushd selinux-policy
+%{__make} -f Makefile.selinux SHARE="%{_datadir}" TARGETS="rpm_hs"
+popd
+
 %install
 %make_install
 
@@ -515,6 +549,9 @@ pushd python
 %py3_install
 popd
 
+install -d -p %{buildroot}%{_datadir}/selinux/packages
+install -p -m 0644 selinux-policy/rpm_hs.pp.bz2 %{buildroot}%{_datadir}/selinux/packages
+
 mkdir -p $RPM_BUILD_ROOT%{_unitdir}
 install -m 644 %{SOURCE10} $RPM_BUILD_ROOT/%{_unitdir}
 install -m 644 %{SOURCE20} $RPM_BUILD_ROOT/%{_unitdir}
@@ -581,6 +618,23 @@ if [ -d /var/lib/rpm ]; then
     touch /var/lib/rpm/.migratedb
 fi
 
+%pre selinux
+%selinux_relabel_pre
+
+%post selinux
+%selinux_modules_install %{_datadir}/selinux/packages/rpm_hs.pp.bz2
+%selinux_relabel_post
+
+%posttrans selinux
+%selinux_relabel_post
+
+%postun selinux
+%selinux_modules_uninstall rpm_hs
+
+if [ $1 -eq 0 ]; then
+    %selinux_relabel_post
+fi
+
 %files -f rpm.lang
 %license COPYING
 %doc CREDITS doc/manual/[a-z]*
@@ -750,6 +804,9 @@ fi
 %license COPYING
 %doc doc/librpm/html/*
 
+%files selinux
+%{_datadir}/selinux/packages/rpm_hs.pp.bz2
+
 %changelog
 * Sun Apr 03 2022 Neal Gompa <ngompa@centosproject.org> - 4.16.1.3-11.3
 - Migrate rpmdb to /usr/lib/sysimage/rpm
diff --git a/rpm_hs.fc b/rpm_hs.fc
new file mode 100644
index 0000000..06999eb
--- /dev/null
+++ b/rpm_hs.fc
@@ -0,0 +1,2 @@
+# This is in /usr, but is expected to be variable content from a policy perspective (#2042149)
+/usr/lib/sysimage/rpm(/.*)?		gen_context(system_u:object_r:rpm_var_lib_t,s0)
diff --git a/rpm_hs.te b/rpm_hs.te
new file mode 100644
index 0000000..e06016b
--- /dev/null
+++ b/rpm_hs.te
@@ -0,0 +1,11 @@
+policy_module(rpm_hs,0.0.1)
+
+# rpm overrides
+gen_require(`
+	type rpm_t;
+	type rpmdb_t;
+	type rpm_var_lib_t;
+')
+
+# Allow rpmdb create directory in /usr/lib/sysimage (#2061141)
+files_usr_filetrans(rpmdb_t, rpm_var_lib_t, dir)