diff --git a/dev/tasks/python-wheels/linux-test.sh b/dev/tasks/python-wheels/linux-test.sh
new file mode 100755
index 0000000..163730a
--- /dev/null
+++ b/dev/tasks/python-wheels/linux-test.sh
@@ -0,0 +1,34 @@
+#!/bin/bash
+
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements.  See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership.  The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License.  You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied.  See the License for the
+# specific language governing permissions and limitations
+# under the License.
+
+# Install built wheel
+pip install /arrow/python/manylinux1/dist/*.whl
+
+# Runs tests on installed distribution from an empty directory
+python --version
+
+# Test optional dependencies
+python -c "import pyarrow"
+python -c "import pyarrow.orc"
+python -c "import pyarrow.parquet"
+python -c "import pyarrow.plasma"
+
+# Run pyarrow tests
+pip install pytest pandas
+pytest --pyargs pyarrow
diff --git a/dev/tasks/python-wheels/travis.linux.yml b/dev/tasks/python-wheels/travis.linux.yml
index 0bb6e69..9a8f804 100644
--- a/dev/tasks/python-wheels/travis.linux.yml
+++ b/dev/tasks/python-wheels/travis.linux.yml
@@ -37,16 +37,24 @@
   - git -C arrow checkout {{ arrow.head }}
   - mkdir -p dist
 
+  # build wheel
   - pushd arrow/python/manylinux1
   - docker run --shm-size=2g
       -e SETUPTOOLS_SCM_PRETEND_VERSION={{ arrow.version }}
-      -e PYTHON_VERSIONS={{ python_version }}
+      -e PYTHON_VERSIONS="{{ python_version }},{{ unicode_width }}"
       -e WHEEL_VERSION={{ wheel_version }}
       -v $PWD:/io
       -v $PWD/../../:/arrow
       quay.io/xhochy/arrow_manylinux1_x86_64_base:latest /io/build_arrow.sh
   - popd
 
+  # test on multiple distributions
+  {%- for image in test_docker_images %}
+  - docker run -it --shm-size 2G --volume $(pwd)/arrow:/arrow {{ image }}
+      /arrow/dev/tasks/python-wheels/linux-test.sh
+  {%- endfor %}
+
+  # prepare for deployment
   - sudo mv arrow/python/manylinux1/dist/* dist/
 
 deploy:
diff --git a/dev/tasks/tasks.yml b/dev/tasks/tasks.yml
index 8353bb2..dec668f 100644
--- a/dev/tasks/tasks.yml
+++ b/dev/tasks/tasks.yml
@@ -143,7 +143,9 @@
     template: python-wheels/travis.linux.yml
     params:
       wheel_version: 0.31.1
-      python_version: 2.7,16
+      python_version: 2.7
+      unicode_width: 16
+      test_docker_images: []
     artifacts:
       - pyarrow-{version}-cp27-cp27m-manylinux1_x86_64.whl
 
@@ -152,7 +154,10 @@
     template: python-wheels/travis.linux.yml
     params:
       wheel_version: 0.31.1
-      python_version: 2.7,32
+      python_version: 2.7
+      unicode_width: 32
+      test_docker_images:
+        - python:2.7-slim  # debian ucs4
     artifacts:
       - pyarrow-{version}-cp27-cp27mu-manylinux1_x86_64.whl
 
@@ -161,7 +166,10 @@
     template: python-wheels/travis.linux.yml
     params:
       wheel_version: 0.31.1
-      python_version: 3.5,16
+      python_version: 3.5
+      unicode_width: 16
+      test_docker_images:
+        - python:3.5-slim
     artifacts:
       - pyarrow-{version}-cp35-cp35m-manylinux1_x86_64.whl
 
@@ -170,7 +178,10 @@
     template: python-wheels/travis.linux.yml
     params:
       wheel_version: 0.31.1
-      python_version: 3.6,16
+      python_version: 3.6
+      unicode_width: 16
+      test_docker_images:
+        - python:3.6-slim
     artifacts:
       - pyarrow-{version}-cp36-cp36m-manylinux1_x86_64.whl
 
@@ -179,7 +190,10 @@
     template: python-wheels/travis.linux.yml
     params:
       wheel_version: 0.31.1
-      python_version: 3.7,16
+      python_version: 3.7
+      unicode_width: 16
+      test_docker_images:
+        - python:3.7-slim
     artifacts:
       - pyarrow-{version}-cp37-cp37m-manylinux1_x86_64.whl