diff --git a/debian/rules b/debian/rules
index 12cb34f..c17b8e6 100755
--- a/debian/rules
+++ b/debian/rules
@@ -21,24 +21,31 @@ ifneq (,$(filter nodoc,$(DEB_BUILD_PROFILES) $(DEB_BUILD_OPTIONS)))
 CONFIGURE_MAN_PAGES = --disable-man-pages
 endif
 
+# The pybuild build system wants to build the Python module for each Python version.
+# We must ensure that Autoconf is triggered in a different build directory each time.
+# Otherwise, the builder will think the source is already built and re-use the binary.
+AUTOTOOLS_ARGS = --buildsystem=autoconf --builddir=.pybuild/autotools-{version}
+# However, Lua tests will not run against all the build trees - only the default version.
+DEFAULT_BUILDDIR = .pybuild/autotools-$(shell py3versions -dv)
+
 export PYBUILD_SYSTEM=custom
-export PYBUILD_CLEAN_ARGS=dh_auto_clean
+export PYBUILD_CLEAN_ARGS=true
 export PYBUILD_CONFIGURE_ARGS=intltoolize --force --automake; \
-	PYTHON={interpreter} dh_auto_configure -- \
+	PYTHON={interpreter} dh_auto_configure $(AUTOTOOLS_ARGS) -- \
 	$(CONFIGURE_MAN_PAGES) --disable-perl --with-systemd
-export PYBUILD_BUILD_ARGS=dh_auto_build
-export PYBUILD_INSTALL_ARGS=dh_auto_install --destdir={destdir}; \
+export PYBUILD_BUILD_ARGS=dh_auto_build $(AUTOTOOLS_ARGS)
+export PYBUILD_INSTALL_ARGS=dh_auto_install $(AUTOTOOLS_ARGS) --destdir={destdir}; \
 	mkdir -p {destdir}/usr/lib/python{version}/dist-packages; \
 	mv {destdir}/usr/lib/python3/dist-packages/_location.so {destdir}/usr/lib/python{version}/dist-packages/_location.so; \
 	rm -f {destdir}/usr/lib/python3/dist-packages/_location.la {destdir}/usr/lib/*/libloc.la
-export PYBUILD_TEST_ARGS=dh_auto_test
+export PYBUILD_TEST_ARGS=dh_auto_test $(AUTOTOOLS_ARGS)
 
 %:
 	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'
+		'LDFROM=$$(OBJECT) -L$(CURDIR)/$(DEFAULT_BUILDDIR)/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
@@ -46,8 +53,8 @@ execute_after_dh_auto_build:
 	set -e; for version in $(LUA_EXTRA_VERSIONS); do \
 		mkdir -p debian/lua$$version; \
 		$(CC) $(CPPFLAGS) $(CFLAGS) $(LDFLAGS) -shared -fPIC \
-			-include config.h -Isrc $$($(PKG_CONFIG) --cflags lua$$version) \
-			-o debian/lua$$version/location.so src/lua/*.c -Lsrc/.libs -lloc; \
+			-include $(DEFAULT_BUILDDIR)/config.h -Isrc $$($(PKG_CONFIG) --cflags lua$$version) \
+			-o debian/lua$$version/location.so src/lua/*.c -L$(DEFAULT_BUILDDIR)/src/.libs -lloc; \
 	done
 
 	dh_auto_build $(PERL_MM)
@@ -66,16 +73,16 @@ execute_after_dh_auto_test:
 ifeq (,$(filter nocheck,$(DEB_BUILD_OPTIONS) $(DEB_BUILD_PROFILES)))
 ifeq ($(DEB_BUILD_ARCH),$(DEB_HOST_ARCH))
 	set -e; for version in $(LUA_EXTRA_VERSIONS); do \
-		LD_LIBRARY_PATH=$(CURDIR)/src/.libs \
+		LD_LIBRARY_PATH=$(CURDIR)/$(DEFAULT_BUILDDIR)/src/.libs \
 		LUA_CPATH="$(CURDIR)/debian/lua$$version/?.so;;" \
 		TEST_DATABASE=$(CURDIR)/data/database.db \
 		TEST_SIGNING_KEY=$(CURDIR)/data/signing-key.pem \
-			lua$$version tests/lua/main.lua; \
+			lua$$version $(DEFAULT_BUILDDIR)/tests/lua/main.lua; \
 	done
 
-	$(MAKE) testdata.db
-	LD_LIBRARY_PATH=$(CURDIR)/src/.libs \
-	database=$(CURDIR)/testdata.db \
+	$(MAKE) -C $(DEFAULT_BUILDDIR) testdata.db
+	LD_LIBRARY_PATH=$(CURDIR)/$(DEFAULT_BUILDDIR)/src/.libs \
+	database=$(CURDIR)/$(DEFAULT_BUILDDIR)/testdata.db \
 	keyfile=$(CURDIR)/examples/public-key.pem \
 		dh_auto_test $(PERL_MM)
 endif