diff --git a/tools/relocation_packer/Android.mk b/tools/relocation_packer/Android.mk
index 35c97a8..2bf77b9 100644
--- a/tools/relocation_packer/Android.mk
+++ b/tools/relocation_packer/Android.mk
@@ -30,7 +30,7 @@
   src/packer.cc \
   src/sleb128.cc \
 
-LOCAL_STATIC_LIBRARIES := libelf
+LOCAL_STATIC_LIBRARIES := libelf libz
 LOCAL_C_INCLUDES := external/elfutils/src/libelf
 LOCAL_MODULE := lib_relocation_packer
 
@@ -45,7 +45,7 @@
 LOCAL_CPP_EXTENSION := .cc
 
 LOCAL_SRC_FILES := src/main.cc
-LOCAL_STATIC_LIBRARIES := lib_relocation_packer libelf
+LOCAL_STATIC_LIBRARIES := lib_relocation_packer libelf libz
 
 # Statically linking libc++ to make it work from prebuilts
 LOCAL_CXX_STL := libc++_static
@@ -70,7 +70,7 @@
   src/sleb128_unittest.cc \
   src/packer_unittest.cc \
 
-LOCAL_STATIC_LIBRARIES := lib_relocation_packer libelf
+LOCAL_STATIC_LIBRARIES := lib_relocation_packer libelf libz
 LOCAL_C_INCLUDES := external/elfutils/src/libelf
 
 LOCAL_CPPFLAGS := $(common_cppflags)