diff --git a/Makefile.am b/Makefile.am
index c74b0cc..aa0f23b 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -1126,6 +1126,8 @@ EXTRA_DIST += \
 	debian/libloc1.symbols \
 	debian/libloc-dev.install \
 	debian/libloc-dev.manpages \
+	debian/liblocation-perl.install \
+	debian/liblocation-perl.manpages \
 	debian/location.install \
 	debian/location.manpages \
 	debian/location.postinst \
diff --git a/debian/control b/debian/control
index c56584b..deb81f8 100644
--- a/debian/control
+++ b/debian/control
@@ -12,6 +12,8 @@ Build-Depends:
  lua-unit:native <!nocheck !cross> | lua-unit <!nocheck !cross>,
  lua5.1 <!nocheck !cross>,
  lua5.4 <!nocheck !cross>,
+ perl-xs-dev,
+ perl:native,
  libssl-dev,
  pkgconf,
  python3-all-dev,
@@ -116,3 +118,15 @@ Description: ${source:Synopsis} (Lua bindings)
  ${source:Extended-Description}
  .
  This package provides the Lua bindings for libloc.
+
+Package: liblocation-perl
+Architecture: any
+Section: perl
+Depends:
+ ${misc:Depends},
+ ${perl:Depends},
+ ${shlibs:Depends},
+Description: ${source:Synopsis} (Perl bindings)
+ ${source:Extended-Description}
+ .
+ This package provides the Perl bindings for libloc.
diff --git a/debian/liblocation-perl.install b/debian/liblocation-perl.install
new file mode 100644
index 0000000..b29dd98
--- /dev/null
+++ b/debian/liblocation-perl.install
@@ -0,0 +1 @@
+usr/lib/*/perl5
diff --git a/debian/liblocation-perl.manpages b/debian/liblocation-perl.manpages
new file mode 100644
index 0000000..1f25cd5
--- /dev/null
+++ b/debian/liblocation-perl.manpages
@@ -0,0 +1 @@
+usr/share/man/man3/Location.3pm*
diff --git a/debian/rules b/debian/rules
index 99c2acf..fe03730 100755
--- a/debian/rules
+++ b/debian/rules
@@ -9,6 +9,12 @@ include /usr/share/dpkg/buildtools.mk
 # because LuaJIT, which PowerDNS uses, loads modules for Lua 5.1.
 LUA_EXTRA_VERSIONS = 5.1
 
+# If the Perl module were built by the Makefile.am, then it would use the build arch's Perl
+# instead of properly cross-compiling. Therefore we add --disable-perl and use debhelper
+# hooks. Linking is done using LDFROM instead of LIBS, as MakeMaker would pull LIBS into
+# the RPATH of the module.
+PERL_MM = --buildsystem=perl_makemaker --sourcedirectory=src/perl
+
 # Build without the manual pages with the nodoc profile, which is needed to cross-compile,
 # because asciidoc cannot be installed for another architecture
 ifneq (,$(filter nodoc,$(DEB_BUILD_PROFILES) $(DEB_BUILD_OPTIONS)))
@@ -30,6 +36,10 @@ export PYBUILD_TEST_ARGS=dh_auto_test
 %:
 	dh $@ --buildsystem=pybuild
 
+execute_after_dh_auto_configure:
+	dh_auto_configure $(PERL_MM) -- INC=-I$(CURDIR)/src LIBS= \
+		'LDFROM=$$(OBJECT) -L$(CURDIR)/src/.libs -lloc'
+
 # The module does not link against Lua, which the program that loads it provides,
 # so that it does not pull in Lua 5.1 when it is being loaded by LuaJIT
 execute_after_dh_auto_build:
@@ -40,13 +50,18 @@ execute_after_dh_auto_build:
 			-o debian/lua$$version/location.so src/lua/*.c -Lsrc/.libs -lloc; \
 	done
 
+	dh_auto_build $(PERL_MM)
+
 execute_after_dh_auto_install:
 	set -e; for version in $(LUA_EXTRA_VERSIONS); do \
 		install -D -m 644 debian/lua$$version/location.so \
 			debian/tmp/usr/lib/$(DEB_HOST_MULTIARCH)/lua/$$version/location.so; \
 	done
 
-# Run the tests of the Lua module with all other versions, too, unless we cannot run them
+	dh_auto_install $(PERL_MM) --destdir=debian/tmp
+
+# Run the tests of the Lua module with all other versions and the Perl module, too,
+# unless we cannot run them due to cross-compilation
 execute_after_dh_auto_test:
 ifeq (,$(filter nocheck,$(DEB_BUILD_OPTIONS) $(DEB_BUILD_PROFILES)))
 ifeq ($(DEB_BUILD_ARCH),$(DEB_HOST_ARCH))
@@ -57,8 +72,16 @@ ifeq ($(DEB_BUILD_ARCH),$(DEB_HOST_ARCH))
 		TEST_SIGNING_KEY=$(CURDIR)/data/signing-key.pem \
 			lua$$version tests/lua/main.lua; \
 	done
+
+	$(MAKE) testdata.db
+	LD_LIBRARY_PATH=$(CURDIR)/src/.libs \
+	database=$(CURDIR)/testdata.db \
+	keyfile=$(CURDIR)/examples/public-key.pem \
+		dh_auto_test $(PERL_MM)
 endif
 endif
 
 execute_after_dh_auto_clean:
 	rm -rf $(foreach version,$(LUA_EXTRA_VERSIONS),debian/lua$(version))
+
+	dh_auto_clean $(PERL_MM)