diff --git a/.gitignore b/.gitignore
index 9c9ae5a..a6b34fd 100644
--- a/.gitignore
+++ b/.gitignore
@@ -4,8 +4,8 @@
 libs
 objs
 
-# Python virtual environment (pre-3.4 only)
-python2.7_virtual_environment
+# Python virtual environments
+python*_virtual_environment
 
 # gcov coverage data
 coverage
diff --git a/.travis.yml b/.travis.yml
index 97cf99d..b6c8062 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -6,7 +6,8 @@
   - echo "deb http://download.mono-project.com/repo/debian wheezy main" | sudo tee /etc/apt/sources.list.d/mono-xamarin.list
   - echo "deb http://download.mono-project.com/repo/debian wheezy-libtiff-compat main" | sudo tee -a /etc/apt/sources.list.d/mono-xamarin.list
   - sudo apt-get update -qq
-  - sudo apt-get install -qq libgtest-dev libgflags-dev python-virtualenv clang-3.5
+  - sudo apt-get install -qq libgtest-dev libgflags-dev python-virtualenv python-dev python3-dev clang-3.5
+  - sudo pip install --upgrade virtualenv
   - sudo pip install cpp-coveralls mako simplejson
   - sudo apt-get install -qq mono-devel nunit
   - wget www.nuget.org/NuGet.exe -O nuget.exe
diff --git a/src/python/src/setup.py b/src/python/src/setup.py
index 70314bb..193285a 100644
--- a/src/python/src/setup.py
+++ b/src/python/src/setup.py
@@ -109,7 +109,12 @@
     list(_EXTENSION_INCLUDE_DIRECTORIES), list(_EXTENSION_LIBRARIES),
     bool(_BUILD_WITH_CYTHON))
 
-_EXTENSION_MODULES = _C_EXTENSION_MODULES + _CYTHON_EXTENSION_MODULES
+# TODO(atash): We shouldn't need to gate any C code based on the python version
+# from the distutils build system. Remove this hackery once we're on Cython and
+# 3.x C API compliant.
+_EXTENSION_MODULES = list(_CYTHON_EXTENSION_MODULES)
+if sys.version_info[0:2] <= (2, 7):
+  _EXTENSION_MODULES += _C_EXTENSION_MODULES
 
 
 _PACKAGES = (
diff --git a/tools/run_tests/build_python.sh b/tools/run_tests/build_python.sh
index 108dd6a..ae0fb42 100755
--- a/tools/run_tests/build_python.sh
+++ b/tools/run_tests/build_python.sh
@@ -35,20 +35,31 @@
 
 root=`pwd`
 
-if [ ! -d 'python2.7_virtual_environment' ]
-then
-  # Build the entire virtual environment
-  virtualenv -p /usr/bin/python2.7 python2.7_virtual_environment
-  source python2.7_virtual_environment/bin/activate
-  pip install -r src/python/requirements.txt
-else
-  source python2.7_virtual_environment/bin/activate
-  # Uninstall and re-install the packages we care about. Don't use
-  # --force-reinstall or --ignore-installed to avoid propagating this
-  # unnecessarily to dependencies. Don't use --no-deps to avoid missing
-  # dependency upgrades.
-  (yes | pip uninstall grpcio) || true
-  (yes | pip uninstall interop) || true
-fi
-CFLAGS="-I$root/include -std=c89" LDFLAGS=-L$root/libs/$CONFIG GRPC_PYTHON_BUILD_WITH_CYTHON=1 pip install src/python/src
-pip install src/python/interop
+make_virtualenv() {
+  virtualenv_name="python"$1"_virtual_environment"
+  if [ ! -d $virtualenv_name ]
+  then
+    # Build the entire virtual environment
+    virtualenv -p `which "python"$1` $virtualenv_name
+    source $virtualenv_name/bin/activate
+    pip install -r src/python/requirements.txt
+    CFLAGS="-I$root/include -std=c89" LDFLAGS=-L$root/libs/$CONFIG GRPC_PYTHON_BUILD_WITH_CYTHON=1 pip install src/python/src
+    pip install src/python/interop
+  else
+    source $virtualenv_name/bin/activate
+    # Uninstall and re-install the packages we care about. Don't use
+    # --force-reinstall or --ignore-installed to avoid propagating this
+    # unnecessarily to dependencies. Don't use --no-deps to avoid missing
+    # dependency upgrades.
+    (yes | pip uninstall grpcio) || true
+    (yes | pip uninstall interop) || true
+    (CFLAGS="-I$root/include -std=c89" LDFLAGS=-L$root/libs/$CONFIG GRPC_PYTHON_BUILD_WITH_CYTHON=1 pip install src/python/src) || (
+      # Fall back to rebuilding the entire environment
+      rm -rf $virtualenv_name
+      make_virtualenv $1
+    )
+    pip install src/python/interop
+  fi
+}
+
+make_virtualenv $1
diff --git a/tools/run_tests/jobset.py b/tools/run_tests/jobset.py
index 8694b8f..1278e77 100755
--- a/tools/run_tests/jobset.py
+++ b/tools/run_tests/jobset.py
@@ -81,6 +81,7 @@
 
 _TAG_COLOR = {
     'FAILED': 'red',
+    'WARNING': 'yellow',
     'TIMEOUT': 'red',
     'PASSED': 'green',
     'START': 'gray',
diff --git a/tools/run_tests/python_tests.json b/tools/run_tests/python_tests.json
index 3bef345..4da4c1b 100755
--- a/tools/run_tests/python_tests.json
+++ b/tools/run_tests/python_tests.json
@@ -1,62 +1,123 @@
 [
   {
-    "module": "grpc._cython.cygrpc_test"
+    "module": "grpc._cython.cygrpc_test",
+    "pythonVersions": [
+      "2.7",
+      "3.4"
+    ]
   },
   {
-    "module": "grpc._cython.adapter_low_test"
+    "module": "grpc._cython.adapter_low_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "grpc._adapter._c_test"
+    "module": "grpc._adapter._c_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "grpc._adapter._low_test"
+    "module": "grpc._adapter._low_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "grpc._adapter._intermediary_low_test"
+    "module": "grpc._adapter._intermediary_low_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "grpc._adapter._links_test"
+    "module": "grpc._adapter._links_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "grpc._adapter._lonely_rear_link_test"
+    "module": "grpc._adapter._lonely_rear_link_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "grpc._adapter._blocking_invocation_inline_service_test"
+    "module": "grpc._adapter._blocking_invocation_inline_service_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "grpc._adapter._event_invocation_synchronous_event_service_test"
+    "module": "grpc._adapter._event_invocation_synchronous_event_service_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "grpc._adapter._future_invocation_asynchronous_event_service_test"
+    "module": "grpc._adapter._future_invocation_asynchronous_event_service_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "grpc.early_adopter.implementations_test"
+    "module": "grpc.early_adopter.implementations_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "grpc.framework.base.implementations_test"
+    "module": "grpc.framework.base.implementations_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "grpc.framework.face.blocking_invocation_inline_service_test"
+    "module": "grpc.framework.face.blocking_invocation_inline_service_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "grpc.framework.face.event_invocation_synchronous_event_service_test"
+    "module": "grpc.framework.face.event_invocation_synchronous_event_service_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "grpc.framework.face.future_invocation_asynchronous_event_service_test"
+    "module": "grpc.framework.face.future_invocation_asynchronous_event_service_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "grpc.framework.foundation._later_test"
+    "module": "grpc.framework.foundation._later_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "grpc.framework.foundation._logging_pool_test"
+    "module": "grpc.framework.foundation._logging_pool_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "interop._insecure_interop_test"
+    "module": "interop._insecure_interop_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "module": "interop._secure_interop_test"
+    "module": "interop._secure_interop_test",
+    "pythonVersions": [
+      "2.7"
+    ]
   },
   {
-    "file": "test/compiler/python_plugin_test.py"
+    "file": "test/compiler/python_plugin_test.py",
+    "pythonVersions": [
+      "2.7"
+    ]
   }
 ]
diff --git a/tools/run_tests/run_python.sh b/tools/run_tests/run_python.sh
index cab08f9..4959c02 100755
--- a/tools/run_tests/run_python.sh
+++ b/tools/run_tests/run_python.sh
@@ -36,5 +36,5 @@
 root=`pwd`
 export LD_LIBRARY_PATH=$root/libs/$CONFIG
 export DYLD_LIBRARY_PATH=$root/libs/$CONFIG
-source python2.7_virtual_environment/bin/activate
-python2.7 -B $*
+source "python"$PYVER"_virtual_environment"/bin/activate
+"python"$PYVER -B $*
diff --git a/tools/run_tests/run_tests.py b/tools/run_tests/run_tests.py
index fd90613..1f44fc3 100755
--- a/tools/run_tests/run_tests.py
+++ b/tools/run_tests/run_tests.py
@@ -189,27 +189,55 @@
   def __init__(self):
     with open('tools/run_tests/python_tests.json') as f:
       self._tests = json.load(f)
+    self._build_python_versions = set([
+        python_version
+        for test in self._tests
+        for python_version in test['pythonVersions']])
+    self._has_python_versions = []
 
   def test_specs(self, config, travis):
-    modules = [config.job_spec(['tools/run_tests/run_python.sh', '-m',
-                                test['module']],
-                               None,
-                               environ=_FORCE_ENVIRON_FOR_WRAPPERS,
-                               shortname=test['module'])
-               for test in self._tests if 'module' in test]
-    files = [config.job_spec(['tools/run_tests/run_python.sh',
-                              test['file']],
-                             None,
-                             environ=_FORCE_ENVIRON_FOR_WRAPPERS,
-                             shortname=test['file'])
-            for test in self._tests if 'file' in test]
-    return files + modules
+    job_specifications = []
+    for test in self._tests:
+      command = None
+      short_name = None
+      if 'module' in test:
+        command = ['tools/run_tests/run_python.sh', '-m', test['module']]
+        short_name = test['module']
+      elif 'file' in test:
+        command = ['tools/run_tests/run_python.sh', test['file']]
+        short_name = test['file']
+      else:
+        raise ValueError('expected input to be a module or file to run '
+                         'unittests from')
+      for python_version in test['pythonVersions']:
+        if python_version in self._has_python_versions:
+          environment = dict(_FORCE_ENVIRON_FOR_WRAPPERS)
+          environment['PYVER'] = python_version
+          job_specifications.append(config.job_spec(
+              command, None, environ=environment, shortname=short_name))
+        else:
+          jobset.message(
+              'WARNING',
+              'Could not find Python {}; skipping test'.format(python_version),
+              '{}\n'.format(command), do_newline=True)
+    return job_specifications
 
   def make_targets(self):
     return ['static_c', 'grpc_python_plugin', 'shared_c']
 
   def build_steps(self):
-    return [['tools/run_tests/build_python.sh']]
+    commands = []
+    for python_version in self._build_python_versions:
+      try:
+        with open(os.devnull, 'w') as output:
+          subprocess.check_call(['which', 'python' + python_version],
+                                stdout=output, stderr=output)
+        commands.append(['tools/run_tests/build_python.sh', python_version])
+        self._has_python_versions.append(python_version)
+      except:
+        jobset.message('WARNING', 'Missing Python ' + python_version,
+                       do_newline=True)
+    return commands
 
   def supports_multi_config(self):
     return False