diff --git a/src/secp256k1/.travis.yml b/src/secp256k1/.travis.yml
--- a/src/secp256k1/.travis.yml
+++ b/src/secp256k1/.travis.yml
@@ -92,6 +92,41 @@
             - libgmp-dev:i386
             - ninja-build
       install: ./travis/install_cmake.sh
+    - compiler: gcc
+      env:
+        - VALGRIND=yes
+        - BIGNUM=no  ENDOMORPHISM=yes  ASM=x86_64  EXPERIMENTAL=yes  ECDH=yes  RECOVERY=yes  OPENSSL_TESTS=no  MULTISET=yes
+        - AUTOTOOLS_EXTRA_FLAGS=CPPFLAGS=-DVALGRIND  AUTOTOOLS_TARGET=
+        - CMAKE_EXTRA_FLAGS=-DCMAKE_C_FLAGS=-DVALGRIND  CMAKE_TARGET="tests exhaustive_tests"
+      addons:
+        apt:
+          packages:
+            - ninja-build
+            - valgrind
+      install: ./travis/install_cmake.sh
+    - compiler: gcc
+      env: # The same as above but without endomorphism.
+        - VALGRIND=yes
+        - BIGNUM=no  ENDOMORPHISM=no  ASM=x86_64  EXPERIMENTAL=yes  ECDH=yes  RECOVERY=yes  OPENSSL_TESTS=no  MULTISET=yes
+        - AUTOTOOLS_EXTRA_FLAGS=CPPFLAGS=-DVALGRIND  AUTOTOOLS_TARGET=
+        - CMAKE_EXTRA_FLAGS=-DCMAKE_C_FLAGS=-DVALGRIND  CMAKE_TARGET="tests exhaustive_tests"
+      addons:
+        apt:
+          packages:
+            - ninja-build
+            - valgrind
+      install: ./travis/install_cmake.sh
+
 script:
  - ./travis/build_autotools.sh
  - ./travis/build_cmake.sh
+ - # travis_wait extends the 10 minutes without output allowed (https://docs.travis-ci.com/user/common-build-problems/#build-times-out-because-no-output-was-received)
+ - # the `--error-exitcode` is required to make the test fail if valgrind found errors, otherwise it'll return 0 (http://valgrind.org/docs/manual/manual-core.html)
+ - if [ -n "$VALGRIND" ]; then
+   travis_wait 30 valgrind --error-exitcode=42 ./buildautotools/tests 16 &&
+   travis_wait 30 valgrind --error-exitcode=42 ./buildautotools/exhaustive_tests;
+   fi
+ - if [ -n "$VALGRIND" ]; then
+   travis_wait 30 valgrind --error-exitcode=42 ./buildcmake/tests 16 &&
+   travis_wait 30 valgrind --error-exitcode=42 ./buildcmake/exhaustive_tests;
+   fi