diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml
index 6db6f32..8a0d1c1 100644
--- a/.gitlab-ci.yml
+++ b/.gitlab-ci.yml
@@ -71,6 +71,9 @@
   script:
     - start_section build_perl_dependencies "Installing Perl dependencies"
     - cpanm -n -l $PERL_LOCAL_LIB_ROOT https://github.com/Akron/Mojolicious-Plugin-Localize.git
+    # Makefile.PL uses Devel::CheckLib to look for libcollocatordb, so it has to
+    # be there before --installdeps can determine the dependencies at all
+    - cpanm -n -l $PERL_LOCAL_LIB_ROOT Devel::CheckLib
     - cpanm -n -l $PERL_LOCAL_LIB_ROOT --installdeps .
     - end_section build_perl_dependencies