diff --git a/ee/app/models/ee/repository.rb b/ee/app/models/ee/repository.rb
index eb9df8d6c7a3943a97e687e845759952e6d16d11..21aba80bc243b5fa73ac67fcecde079c93597f67 100644
--- a/ee/app/models/ee/repository.rb
+++ b/ee/app/models/ee/repository.rb
@@ -21,5 +21,13 @@ def new_commits(newrev)
 
       refs.map { |sha| commit(sha.strip) }
     end
+
+    def new_blobs(newrev)
+      rev_list = ::Gitlab::Git::RevList.new(
+        path_to_repo: path_to_repo,
+        newrev: newrev)
+
+      rev_list.new_blobs(project)
+    end
   end
 end
diff --git a/lib/gitlab/checks/change_access.rb b/lib/gitlab/checks/change_access.rb
index 6f89a826b03b58119790a52e19eb72dc6a549c61..6ff663329482c773607b8a5cec78802a7b77863b 100644
--- a/lib/gitlab/checks/change_access.rb
+++ b/lib/gitlab/checks/change_access.rb
@@ -14,7 +14,8 @@ class ChangeAccess
         change_existing_tags: 'You are not allowed to change existing tags on this project.',
         update_protected_tag: 'Protected tags cannot be updated.',
         delete_protected_tag: 'Protected tags cannot be deleted.',
-        create_protected_tag: 'You are not allowed to create this tag as it is protected.'
+        create_protected_tag: 'You are not allowed to create this tag as it is protected.',
+        lfs_objects_missing: 'LFS objects are missing. Ensure LFS is properly set up or try a manual "git lfs push --all".'
       }.freeze
 
       # protocol is currently used only in EE
@@ -40,6 +41,7 @@ def exec
         branch_checks
         tag_checks
         push_rule_check
+        lfs_objects_exist_check
 
         true
       end
@@ -170,6 +172,25 @@ def push_rule_check
         end
       end
 
+      def lfs_objects_exist_check
+        return unless @newrev
+
+        # return if lfs not enabled for the repo
+
+        #TODO: Is there a need to check files actually exist when
+        # they have an LfsObject?
+
+        #TODO: Do we need a way to bypass this if `git lfs push --all` fails to work?
+
+        new_lfs_blobs = new_blobs.select(&:lfs_oid)
+
+        existing_count = LfsObject.where(oid: new_lfs_blobs.map(&:lfs_oid)).count
+
+        if existing_count != new_lfs_blobs.count
+          raise GitAccess::UnauthorizedError, ERROR_MESSAGES[:lfs_objects_missing]
+        end
+      end
+
       def tag_deletion_denied_by_push_rule?(push_rule)
         push_rule.try(:deny_delete_tag) &&
           protocol != 'web' &&
@@ -289,6 +310,10 @@ def file_size_validation(commit, max_file_size)
       def commits
         project.repository.new_commits(@newrev)
       end
+
+      def new_blobs
+        project.repository.new_blobs(@newrev)
+      end
     end
   end
 end
diff --git a/lib/gitlab/git/blob.rb b/lib/gitlab/git/blob.rb
index db6cfc9671f26cc6e0a4759669b5ff5c91d6072b..6688b40e1c37f7517b22a1ca86a3eb4f43526840 100644
--- a/lib/gitlab/git/blob.rb
+++ b/lib/gitlab/git/blob.rb
@@ -90,17 +90,20 @@ def raw(repository, sha)
               Gitlab::GitalyClient::BlobService.new(repository).get_blob(oid: sha, limit: MAX_DATA_DISPLAY_SIZE)
             else
               blob = repository.lookup(sha)
-
-              new(
-                id: blob.oid,
-                size: blob.size,
-                data: blob.content(MAX_DATA_DISPLAY_SIZE),
-                binary: blob.binary?
-              )
+              from_rugged_blob(blob)
             end
           end
         end
 
+        def from_rugged_blob(blob)
+          new(
+            id: blob.oid,
+            size: blob.size,
+            data: blob.content(MAX_DATA_DISPLAY_SIZE),
+            binary: blob.binary?
+          )
+        end
+
         def binary?(data)
           # EncodingDetector checks the first 1024 * 1024 bytes for NUL byte, libgit2 checks
           # only the first 8000 (https://github.com/libgit2/libgit2/blob/2ed855a9e8f9af211e7274021c2264e600c0f86b/src/filter.h#L15),
diff --git a/lib/gitlab/git/rev_list.rb b/lib/gitlab/git/rev_list.rb
index 2b5785a1f089ff7d9071f98bcd8cb5eb06ac46fe..f7ea7e90d907c49de6f607dbb5b5de60bbf90ab1 100644
--- a/lib/gitlab/git/rev_list.rb
+++ b/lib/gitlab/git/rev_list.rb
@@ -16,6 +16,46 @@ def new_refs
         execute([*base_args, newrev, '--not', '--all'])
       end
 
+      # Find newly added blobs
+      # Returns array of Gitlab::Git::Blob
+      def new_blobs(project)
+        new_objects.map do |output_line|
+          sha, path = output_line.split(' ', 2)
+
+          Addition.new(sha, path, project)
+        end.map(&:blob).compact
+      end
+
+      class Addition
+        def initialize(sha, path, project)
+          @sha = sha
+          @path = path
+          @project = project
+        end
+
+        def blob
+          return unless @path
+          return @blob if defined?(@blob)
+
+          @blob = if object.is_a?(Rugged::Blob)
+            Gitlab::Git::Blob.from_rugged_blob(object)
+          else
+            nil
+          end
+        end
+
+        alias_method :blob?, :blob
+
+        def object
+          return @object if defined?(@object)
+
+          #TODO: Use Gitlab::Git::Blob.raw(repository, sha)
+          # Would need to make it return nil for Tree objects with
+          # both Rugged and with Gitaly
+          @object = @project.repository.lookup(@sha)
+        end
+      end
+
       # This methods returns an array of missed references
       #
       # Should become obsolete after https://gitlab.com/gitlab-org/gitaly/issues/348.
@@ -42,6 +82,10 @@ def base_args
           'rev-list'
         ]
       end
+
+      def new_objects
+        output = execute([*base_args, newrev, '--not', '--all', '--objects'])
+      end
     end
   end
 end