After some struggles with some missing documentation I finally did it.

Step 1

Create a bucket and an IAM-User with the recommended policy from  docs.docker.com.

#Step 2
Use this conf in /etc/gitlab/gitlab.rb: (Don’t forget the region)

registry['storage'] = {
  's3' => {
    'accesskey' => 'ACCESS_KEY',
    'secretkey' => 'SECRET_ACCESS_KEY',
    'bucket' => 'S3_BUCKET_NAME',
    'region' => 'S3_REGION' # e.g. 'eu-central-1'
  }
}

Step 3

(This is the step that drove me almost mad)
Create a folder named “test” in the bucket

Step 4

Start your CI and enjoy your success!