diff --git a/.gitignore b/.gitignore
index 15e82f96f2361c8b22deb300d5148c52f44e3247..8485277d1e526646e2ebbdf89d6cf6863662eed5 100644
--- a/.gitignore
+++ b/.gitignore
@@ -2,3 +2,6 @@
 /_build
 /gitaly
 /gitaly-client
+/*.deb
+/_package/bin
+/_package/.bundle/
diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml
index 04addd180b905c12f5222f8a22c2bdabd59bd5b6..d165681d789bf64e3262d4f797232cb5ed5baa30 100644
--- a/.gitlab-ci.yml
+++ b/.gitlab-ci.yml
@@ -1,6 +1,43 @@
 image: golang:1.7
 
+stages:
+  - test
+  - package
+  - publish
+
 test:
+  stage: test
   script:
     - make
     - make test
+
+package:
+  stage: package
+  only: 
+    - tags
+  script:
+    - apt-get update -qq
+    - apt-get install -qq -y rubygems bundler
+    - GOOS=linux GOARCH=amd64 make clean package
+    - ls -l # Want to see permissions as they went into the .deb
+    - dpkg -e *.deb
+    - cat DEBIAN/control
+    - cat DEBIAN/md5sums
+    - rm -rf DEBIAN
+  artifacts:
+    paths:
+      - ./*.deb
+
+publish:
+  stage: publish
+  only:
+    - tags
+  variables:
+    GIT_STRATEGY: none
+  script:
+    - apt-get update -qq
+    - apt-get install -y rubygems
+    - gem install package_cloud
+    - ls -lh *.deb
+    - shasum -a256 *.deb
+    - package_cloud push $PACKAGECLOUD_REPO *.deb --url=https://packages.gitlab.com
diff --git a/Makefile b/Makefile
index 023b39753ef30328504a66d04360baa87fa922e5..29ea25e4e80c6aa19e602c8f9ad8b28d93f099f5 100644
--- a/Makefile
+++ b/Makefile
@@ -26,6 +26,9 @@ test: clean-build ${BUILD_DIR}/_build fmt
 fmt:
 	_support/gofmt-all -n | awk '{ print } END { if (NR > 0) { print "Please run _support/gofmt-all -f"; exit 1 } }'
 
+package:	build
+	./_package/package ${CMDS}
+
 clean:	clean-build
 	rm -rf client/testdata
 	rm -f $(foreach cmd,${CMDS},./${cmd})
diff --git a/_package/Gemfile b/_package/Gemfile
new file mode 100644
index 0000000000000000000000000000000000000000..cf5bae70ec1f2616d5f8c20ba9a005ab5cdc475d
--- /dev/null
+++ b/_package/Gemfile
@@ -0,0 +1,5 @@
+# frozen_string_literal: true
+# A sample Gemfile
+source 'https://rubygems.org'
+
+gem 'fpm'
diff --git a/_package/Gemfile.lock b/_package/Gemfile.lock
new file mode 100644
index 0000000000000000000000000000000000000000..9eac985a84b8b917d7151e4b83f5ef0bc2de184e
--- /dev/null
+++ b/_package/Gemfile.lock
@@ -0,0 +1,48 @@
+GEM
+  remote: https://rubygems.org/
+  specs:
+    archive-tar-minitar (0.5.2)
+    arr-pm (0.0.10)
+      cabin (> 0)
+    backports (3.6.8)
+    cabin (0.9.0)
+    childprocess (0.5.9)
+      ffi (~> 1.0, >= 1.0.11)
+    clamp (1.0.1)
+    dotenv (2.1.1)
+    ffi (1.9.14)
+    fpm (1.8.0)
+      archive-tar-minitar
+      arr-pm (~> 0.0.10)
+      backports (>= 2.6.2)
+      cabin (>= 0.6.0)
+      childprocess
+      clamp (~> 1.0.0)
+      ffi
+      json (>= 1.7.7, < 2.0)
+      pleaserun (~> 0.0.24)
+      ruby-xz
+    insist (1.0.0)
+    io-like (0.3.0)
+    json (1.8.3)
+    mustache (0.99.8)
+    pleaserun (0.0.27)
+      cabin (> 0)
+      clamp
+      dotenv
+      insist
+      mustache (= 0.99.8)
+      stud
+    ruby-xz (0.2.3)
+      ffi (~> 1.9)
+      io-like (~> 0.3)
+    stud (0.0.22)
+
+PLATFORMS
+  ruby
+
+DEPENDENCIES
+  fpm
+
+BUNDLED WITH
+   1.12.5
diff --git a/_package/package b/_package/package
new file mode 100755
index 0000000000000000000000000000000000000000..cc9ef8cab1674039eddd2394a76127025761f72b
--- /dev/null
+++ b/_package/package
@@ -0,0 +1,40 @@
+#!/usr/bin/env ruby
+
+NAME = 'gitaly'
+DESCRIPTION = 'Gitaly (part of GitLab). Experimental build for testing only.'
+VERSION = IO.popen(%w[git describe]) { |io| io.read }.chomp.split('v', 2)[1]
+ARCHITECTURE = 'amd64'
+PREFIX = '/usr/local'
+VENDOR = 'GitLab Inc.'
+MAINTAINER = VENDOR
+LICENSE = 'MIT'
+URL = 'https://gitlab.com/gitlab-org/gitaly'
+
+PACKAGE_DIR = File.dirname(__FILE__)
+
+def main(args)
+  run!(%w[bundle install --quiet --binstubs], PACKAGE_DIR)
+  File.chmod(0755, *args)
+  File.chmod(0644, 'NOTICE')
+  fpm = %W[
+    #{PACKAGE_DIR}/bin/fpm -t deb -m #{MAINTAINER} --vendor #{VENDOR} --license #{LICENSE}
+    --url #{URL} -s dir -n #{NAME} -v #{VERSION} -a #{ARCHITECTURE} --description #{DESCRIPTION}
+  ]
+  fpm += args.map { |arg| "#{arg}=#{PREFIX}/bin/" }
+  fpm << "NOTICE=usr/share/doc/#{NAME}/"
+  run!(fpm, '.')
+end
+
+def run!(cmd, dir)
+  if ! system(*cmd, chdir: dir)
+    abort "command failed: #{cmd.join(' ')}"
+  end
+end
+
+abort "VERSION cannot be empty" if VERSION.empty?
+
+if ARGV.empty?
+  abort "Usage: #{$0} EXECUTABLE [EXECUTABLE...]"
+end
+
+main(ARGV)