diff --git a/.travis.yml b/.travis.yml
index c36e721a5e1d..bd3c98420c24 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -34,6 +34,14 @@ matrix:
       env: PYVER=python3.8 RUBYLIBVER=2.7 LINKER=gold
     - compiler: clang
       env: PYVER=python3.8 RUBYLIBVER=2.7 LINKER=bfd
+  include:
+    - compiler: gcc
+      env: TRAVIS_RUN_KVM=true TRAVIS_CLOUD_IMAGE_VERSION="32:1.6"
+      install:
+        - skip
+      before_script:
+        - skip
+      script: scripts/ci/travis-kvm-setup.sh
 
 # Use Travis-CI Ubuntu 18.04 Bionic Beaver, "full image" variant
 sudo: required
diff --git a/scripts/ci/README.md b/scripts/ci/README.md
new file mode 100644
index 000000000000..04a134a438c2
--- /dev/null
+++ b/scripts/ci/README.md
@@ -0,0 +1,8 @@
+# Continuous Integration Scripts
+
+The scripts under `scripts/ci` are designed specifically
+for the Travis CI system. While nothing prevents you
+from mimicking that environment and using them locally,
+they are not applicable for general consumption. Any
+thing in this directory should never be considered as
+a stable API.
diff --git a/scripts/ci/fedora-test-runner.sh b/scripts/ci/fedora-test-runner.sh
new file mode 100755
index 000000000000..0927ed5dad8f
--- /dev/null
+++ b/scripts/ci/fedora-test-runner.sh
@@ -0,0 +1,87 @@
+#!/usr/bin/env bash
+
+set -ev
+
+# CI Debug output if things go squirrely.
+getenforce
+id -Z
+nproc
+pwd
+
+# Turn off enforcing for the setup to prevent any weirdness from breaking
+# the CI.
+setenforce 0
+
+dnf clean all -y
+dnf install -y \
+    --allowerasing \
+    --skip-broken \
+    git \
+    audit-libs-devel \
+    bison \
+    bzip2-devel \
+    CUnit-devel \
+    diffutils \
+    flex \
+    gcc \
+    gettext \
+    glib2-devel \
+    make \
+    libcap-devel \
+    libcap-ng-devel \
+    pam-devel \
+    pcre-devel \
+    xmlto \
+    python3-devel \
+    ruby-devel \
+    swig \
+    perl-Test \
+    perl-Test-Harness \
+    perl-Test-Simple \
+    selinux-policy-devel \
+    gcc \
+    libselinux-devel \
+    net-tools \
+    netlabel_tools \
+    iptables \
+    lksctp-tools-devel \
+    attr \
+    libbpf-devel \
+    keyutils-libs-devel \
+    kernel-devel \
+    quota \
+    xfsprogs-devel \
+    libuuid-devel \
+    kernel-devel-"$(uname -r)" \
+    kernel-modules-"$(uname -r)"
+
+#
+# Move to selinux code and build
+#
+cd "$HOME/selinux"
+
+# Show HEAD commit for sanity checking
+git log -1
+
+#
+# Build and replace userspace components
+#
+make -j"$(nproc)" LIBDIR=/usr/lib64 SHLIBDIR=/lib64 install
+make -j"$(nproc)" LIBDIR=/usr/lib64 SHLIBDIR=/lib64 install-pywrap
+make -j"$(nproc)" LIBDIR=/usr/lib64 SHLIBDIR=/lib64 relabel
+
+#
+# Get the selinux testsuite, but don't clone it in $HOME/selinux, move to $HOME
+# first.
+#
+cd "$HOME"
+git clone --depth=1 https://github.com/SELinuxProject/selinux-testsuite.git
+cd selinux-testsuite
+
+# The testsuite must be run in enforcing mode
+setenforce 1
+
+#
+# Run the test suite
+#
+make test
diff --git a/scripts/ci/travis-kvm-setup.sh b/scripts/ci/travis-kvm-setup.sh
new file mode 100755
index 000000000000..864dbac96a46
--- /dev/null
+++ b/scripts/ci/travis-kvm-setup.sh
@@ -0,0 +1,125 @@
+#!/usr/bin/env bash
+
+set -ev
+
+TEST_RUNNER="scripts/ci/fedora-test-runner.sh"
+
+#
+# Variables for controlling the Fedora Image version and download URLs.
+#
+MAJOR_VERSION="32"
+MINOR_VERSION="1.6"
+
+BASE_URL="https://download.fedoraproject.org/pub/fedora/linux/releases"
+IMAGE_BASE_NAME="Fedora-Cloud-Base-$MAJOR_VERSION-$MINOR_VERSION.x86_64"
+IMAGE_URL="$BASE_URL/$MAJOR_VERSION/Cloud/x86_64/images/$IMAGE_BASE_NAME.raw.xz"
+CHECK_URL="$BASE_URL/$MAJOR_VERSION/Cloud/x86_64/images/Fedora-Cloud-$MAJOR_VERSION-$MINOR_VERSION-x86_64-CHECKSUM"
+GPG_URL="https://getfedora.org/static/fedora.gpg"
+
+#
+# Travis gives us 7.5GB of RAM and two cores:
+# https://docs.travis-ci.com/user/reference/overview/
+#
+MEMORY=4096
+VCPUS="$(nproc)"
+
+# Install these here so other builds don't have to wait on these deps to download and install
+sudo apt-get install qemu-kvm libvirt-bin virtinst bridge-utils cpu-checker libguestfs-tools
+
+sudo usermod -a -G kvm,libvirt,libvirt-qemu "$USER"
+
+# Verify that KVM is working, useful if Travis ever changes anything.
+kvm-ok
+
+sudo systemctl enable libvirtd
+sudo systemctl start libvirtd
+
+# Set up a key so we can ssh into the VM
+ssh-keygen -N "" -f "$HOME/.ssh/id_rsa"
+
+#
+# Get the Fedora Cloud Image, It is a base image that small and ready to go, extract it and modify it with virt-sysprep
+#  - https://alt.fedoraproject.org/en/verify.html
+cd "$HOME"
+wget "$IMAGE_URL"
+
+# Verify the image
+curl "$GPG_URL" | gpg --import
+wget "$CHECK_URL"
+gpg --verify-files ./*-CHECKSUM
+sha256sum --ignore-missing -c ./*-CHECKSUM
+
+# Extract the image
+unxz -T0 "$IMAGE_BASE_NAME.raw.xz"
+
+# Search is needed for $HOME so virt service can access the image file.
+chmod a+x "$HOME"
+
+#
+# Modify the virtual image to:
+#   - Enable a login, we just use root
+#   - Enable passwordless login
+#     - Force a relabel to fix labels on ssh keys
+#
+sudo virt-sysprep -a "$IMAGE_BASE_NAME.raw" \
+  --root-password password:123456 \
+  --hostname fedoravm \
+  --append-line '/etc/ssh/sshd_config:PermitRootLogin yes' \
+  --append-line '/etc/ssh/sshd_config:PubkeyAuthentication yes' \
+  --mkdir /root/.ssh \
+  --upload "$HOME/.ssh/id_rsa.pub:/root/.ssh/authorized_keys" \
+  --chmod '0600:/root/.ssh/authorized_keys' \
+  --run-command 'chown root:root /root/.ssh/authorized_keys' \
+  --copy-in "$TRAVIS_BUILD_DIR:/root" \
+  --network \
+  --selinux-relabel
+
+#
+# Now we create a domain by using virt-install. This not only creates the domain, but runs the VM as well
+# It should be ready to go for ssh, once ssh starts.
+#
+sudo virt-install \
+  --name fedoravm \
+  --memory $MEMORY \
+  --vcpus $VCPUS \
+  --disk "$IMAGE_BASE_NAME.raw" \
+  --import --noautoconsole
+
+#
+# Here comes the tricky part, we have to figure out when the VM comes up AND we need the ip address for ssh. So we
+# can check the net-dhcp leases, for our host. We have to poll, and we will poll for up to 3 minutes in 6 second
+# intervals, so 30 poll attempts (0-29 inclusive).
+#
+# We have a full reboot + relabel, so first sleep gets us close
+#
+sleep 30
+for i in $(seq 0 29); do
+    echo "loop $i"
+    sleep 6s
+    # Get the leases, but tee it so it's easier to debug
+    sudo virsh net-dhcp-leases default | tee dhcp-leases.txt
+
+    # get our ipaddress
+    ipaddy="$(grep fedoravm dhcp-leases.txt | awk '{print $5}' | cut -d'/' -f 1-1)"
+    if [ -n "$ipaddy" ]; then
+        # found it, we're done looking, print it for debug logs
+        echo "ipaddy: $ipaddy"
+        break
+    fi
+    # it's empty/not found, loop back and try again.
+done
+
+# Did we find it? If not die.
+if [ -z "$ipaddy" ]; then
+    echo "ipaddy zero length, exiting with error 1"
+    exit 1
+fi
+
+#
+# Great we have a host running, ssh into it. We specify -o so
+# we don't get blocked on asking to add the servers key to
+# our known_hosts.
+#
+ssh -tt -o StrictHostKeyChecking=no -o LogLevel=QUIET "root@$ipaddy" "/root/selinux/$TEST_RUNNER"
+
+exit 0
