diff --git a/CHANGELOG-EE b/CHANGELOG-EE
index a4be3699f5a7eed38e86caee59e65efbb34e827b..4624c50b1f872919b0a6ee72bb34d1d2137d7d03 100644
--- a/CHANGELOG-EE
+++ b/CHANGELOG-EE
@@ -7,6 +7,7 @@ v 8.12.0 (Unreleased)
   - Add 'Sync now' to group members page !704
   - [ES] Instrument other Gitlab::Elastic classes
   - [ES] Fix: Elasticsearch does not find partial matches in project names
+  - Faster Active Directory group membership resolution !719
   - [ES] Global code search
   - [ES] Improve logging
   - Fix projects with remote mirrors asynchronously destruction
diff --git a/lib/ee/gitlab/ldap/adapter.rb b/lib/ee/gitlab/ldap/adapter.rb
index a2aa35e25063e9c6e73215797cdec6738e45a528..a718d94e3c8e2500d6074cee37789c2b71ede958 100644
--- a/lib/ee/gitlab/ldap/adapter.rb
+++ b/lib/ee/gitlab/ldap/adapter.rb
@@ -31,13 +31,26 @@ def group(*args)
           groups(*args).first
         end
 
-        def dns_for_filter(filter)
+        def group_members_in_range(dn, range_start)
           ldap_search(
-            base: config.base,
-            filter: filter,
-            scope: Net::LDAP::SearchScope_WholeSubtree,
-            attributes: %w{dn}
-          ).map(&:dn)
+            base: dn,
+            scope: Net::LDAP::SearchScope_BaseObject,
+            attributes: ["member;range=#{range_start}-*"],
+          ).first
+        end
+
+        def nested_groups(parent_dn)
+          options = {
+            base: config.group_base,
+            filter: Net::LDAP::Filter.join(
+              Net::LDAP::Filter.eq('objectClass', 'group'),
+              Net::LDAP::Filter.eq('memberOf', parent_dn)
+            )
+          }
+
+          ldap_search(options).map do |entry|
+            LDAP::Group.new(entry, self)
+          end
         end
       end
     end
diff --git a/lib/ee/gitlab/ldap/group.rb b/lib/ee/gitlab/ldap/group.rb
index 6ed5a548cbd6eef7716e504fc67ec915cae47b3b..09a390fa8ae19434e65d09ef45a0b5e909c654a1 100644
--- a/lib/ee/gitlab/ldap/group.rb
+++ b/lib/ee/gitlab/ldap/group.rb
@@ -39,14 +39,15 @@ def member_uids
           entry.memberuid
         end
 
-        def member_dns
+        def dn
+          entry.dn
+        end
+
+        def member_dns(nested_groups_to_skip = [])
           dns = []
 
-          # There's an edge-case with AD where sometimes a recursive search
-          # doesn't return all users at the top-level. Concat recursive results
-          # with regular results to be safe. See gitlab-ee#484
-          if active_directory?
-            dns = adapter.dns_for_filter(active_directory_recursive_memberof_filter)
+          if active_directory? && adapter
+            dns.concat(active_directory_members(entry, nested_groups_to_skip))
           end
 
           if (entry.respond_to? :member) && (entry.respond_to? :submember)
@@ -60,20 +61,91 @@ def member_dns
           else
             Rails.logger.warn("Could not find member DNs for LDAP group #{entry.inspect}")
           end
+
           dns.uniq
         end
 
         private
 
-        # We use the ActiveDirectory LDAP_MATCHING_RULE_IN_CHAIN matching rule; see
-        # http://msdn.microsoft.com/en-us/library/aa746475%28VS.85%29.aspx#code-snippet-5
-        def active_directory_recursive_memberof_filter
-          Net::LDAP::Filter.ex("memberOf:1.2.840.113556.1.4.1941", entry.dn)
-        end
-
         def entry
           @entry
         end
+
+        # Active Directory range member methods
+
+        def has_member_range?(entry)
+          member_range_attribute(entry).present?
+        end
+
+        def member_range_attribute(entry)
+          entry.attribute_names.find { |a| a.to_s.start_with?("member;range=")}.to_s
+        end
+
+        def active_directory_members(entry, nested_groups_to_skip)
+          require 'net/ldap/dn'
+
+          members = []
+
+          # Retrieve all member pages/ranges
+          members.concat(ranged_members(entry)) if has_member_range?(entry)
+          # Process nested group members
+          members.concat(nested_members(nested_groups_to_skip))
+
+          # Clean dns of groups and users outside the base
+          members.reject! { |dn| nested_groups_to_skip.include?(dn) }
+          base = Net::LDAP::DN.new(adapter.config.base.downcase).to_a
+          members.select! { |dn| Net::LDAP::DN.new(dn.downcase).to_a.last(base.length) == base }
+
+          members
+        end
+
+        # AD requires use of range retrieval for groups with more than 1500 members
+        # cf. https://msdn.microsoft.com/en-us/library/aa367017(v=vs.85).aspx
+        def ranged_members(entry)
+          members = []
+
+          # Concatenate the members in the current range
+          members.concat(entry[member_range_attribute(entry)])
+
+          # Recursively concatenate members until end of ranges
+          if has_more_member_ranges?(entry)
+            next_entry = adapter.group_members_in_range(dn, next_member_range_start(entry))
+
+            members.concat(ranged_members(next_entry))
+          end
+
+          members
+        end
+
+        # Process any AD nested groups. Use a manual process because
+        # the AD recursive member of filter is too slow and uses too
+        # much CPU on the AD server.
+        def nested_members(nested_groups_to_skip)
+          # Ignore this group if we see it again in a nested group.
+          # Prevents infinite loops.
+          nested_groups_to_skip << dn
+
+          members = []
+          nested_groups = adapter.nested_groups(dn)
+
+          nested_groups.each do |nested_group|
+            next if nested_groups_to_skip.include?(nested_group.dn)
+
+            members.concat(nested_group.member_dns(nested_groups_to_skip))
+          end
+
+          members
+        end
+
+        def has_more_member_ranges?(entry)
+          next_member_range_start(entry).present?
+        end
+
+        def next_member_range_start(entry)
+          match = member_range_attribute(entry).match /^member;range=\d+-(\d+|\*)$/
+
+          match[1].to_i + 1 if match.present? && match[1] != '*'
+        end
       end
     end
   end
diff --git a/spec/lib/ee/gitlab/ldap/group_spec.rb b/spec/lib/ee/gitlab/ldap/group_spec.rb
index 3ea5cb87f7fbf08eee541ddc42883ecb0c933fdc..054db487245b7b80e840bf250035368750458f0f 100644
--- a/spec/lib/ee/gitlab/ldap/group_spec.rb
+++ b/spec/lib/ee/gitlab/ldap/group_spec.rb
@@ -3,47 +3,125 @@
 describe EE::Gitlab::LDAP::Group, lib: true do
   include LdapHelpers
 
-  let(:adapter) { ldap_adapter }
+  before do
+    stub_ldap_config(active_directory: true)
+  end
 
   describe '#member_dns' do
-    def ldif
-      Net::LDAP::Entry.from_single_ldif_string(
-        <<-EOS.strip_heredoc
-          dn: cn=ldap_group1,ou=groups,dc=example,dc=com
-          cn: ldap_group1
-          description: LDAP Group 1
-          member: uid=user1,ou=users,dc=example,dc=com
-          member: uid=user2,ou=users,dc=example,dc=com
-          member: uid=user3,ou=users,dc=example,dc=com
-          objectclass: top
-          objectclass: groupOfNames
-        EOS
+    let(:adapter) { ldap_adapter }
+
+    it 'resolves the correct member_dns when member has a range' do
+      group_entry_page1 = ldap_group_entry_with_member_range(
+        [user_dn('user1'), user_dn('user2'), user_dn('user3')],
+        range_start: '0',
+        range_end: '2'
       )
-    end
+      group_entry_page2 = ldap_group_entry_with_member_range(
+        [user_dn('user4'), user_dn('user5'), user_dn('user6')],
+        range_start: '3',
+        range_end: '*'
+      )
+      group = EE::Gitlab::LDAP::Group.new(group_entry_page1, adapter)
+      stub_ldap_adapter_group_members_in_range(group_entry_page2, adapter, range_start: '3')
+      stub_ldap_adapter_nested_groups(group.dn, [], adapter)
 
-    let(:group) { described_class.new(ldif, adapter) }
-    let(:recursive_dns) do
-      %w(
-        uid=user3,ou=users,dc=example,dc=com
-        uid=user4,ou=users,dc=example,dc=com
-        uid=user5,ou=users,dc=example,dc=com
+      expect(group.member_dns).to match_array(
+        %w(
+          uid=user1,ou=users,dc=example,dc=com
+          uid=user2,ou=users,dc=example,dc=com
+          uid=user3,ou=users,dc=example,dc=com
+          uid=user4,ou=users,dc=example,dc=com
+          uid=user5,ou=users,dc=example,dc=com
+          uid=user6,ou=users,dc=example,dc=com
+        )
       )
     end
 
-    it 'concatenates recursive and regular results and returns uniq' do
-      allow(group).to receive(:active_directory?).and_return(true)
-      allow(adapter).to receive(:dns_for_filter).and_return(recursive_dns)
+    context 'when there are nested groups' do
+      let(:group1_entry) do
+        ldap_group_entry(
+          [user_dn('user1'), user_dn('user2')],
+          objectclass: 'group',
+          member_attr: 'member'
+        )
+      end
+      let(:group2_entry) do
+        ldap_group_entry(
+          [user_dn('user3'), user_dn('user4')],
+          cn: 'ldap_group2',
+          objectclass: 'group',
+          member_attr: 'member',
+          member_of: group1_entry.dn
+        )
+      end
+      let(:group) { EE::Gitlab::LDAP::Group.new(group1_entry, adapter) }
+
+      it 'resolves the correct member_dns when there are nested groups' do
+        group3_entry = ldap_group_entry(
+          [user_dn('user5'), user_dn('user6')],
+          cn: 'ldap_group3',
+          objectclass: 'group',
+          member_attr: 'member',
+          member_of: group1_entry.dn
+        )
+        nested_groups = [group2_entry, group3_entry]
+        stub_ldap_adapter_nested_groups(group.dn, nested_groups, adapter)
+        stub_ldap_adapter_nested_groups(group2_entry.dn, [], adapter)
+        stub_ldap_adapter_nested_groups(group3_entry.dn, [], adapter)
 
-      expect(group.member_dns)
-        .to match_array(
+        expect(group.member_dns).to match_array(
           %w(
             uid=user1,ou=users,dc=example,dc=com
             uid=user2,ou=users,dc=example,dc=com
             uid=user3,ou=users,dc=example,dc=com
             uid=user4,ou=users,dc=example,dc=com
             uid=user5,ou=users,dc=example,dc=com
+            uid=user6,ou=users,dc=example,dc=com
           )
         )
+      end
+
+      it 'skips duplicate nested groups' do
+        group3_entry = ldap_group_entry(
+          [user_dn('user5'), user_dn('user6')],
+          cn: 'ldap_group3',
+          objectclass: 'group',
+          member_attr: 'member',
+          member_of: [group1_entry.dn, group2_entry.dn]
+        )
+        nested_groups = [group2_entry, group3_entry]
+        stub_ldap_adapter_nested_groups(group.dn, nested_groups, adapter)
+        stub_ldap_adapter_nested_groups(group2_entry.dn, [group3_entry], adapter)
+        stub_ldap_adapter_nested_groups(group3_entry.dn, [], adapter)
+
+        expect(adapter).to receive(:nested_groups).with(group3_entry.dn).once
+
+        group.member_dns
+      end
+
+      it 'does not include group dns or users outside of the base' do
+        # Spaces in the 3rd DN below are intentional to ensure we're sanitizing
+        # DNs before comparing and not just doing a string compare.
+        group3_entry = ldap_group_entry(
+          [
+            'cn=ldap_group2,ou=groups,dc=example,dc=com',
+            'uid=foo,ou=users,dc=other,dc=com',
+            'uid=bar,ou=users,dc=example , dc=com'
+          ],
+          cn: 'ldap_group3',
+          objectclass: 'group',
+          member_attr: 'member',
+          member_of: group1_entry.dn
+        )
+        nested_groups = [group2_entry, group3_entry]
+        stub_ldap_adapter_nested_groups(group.dn, nested_groups, adapter)
+        stub_ldap_adapter_nested_groups(group2_entry.dn, [], adapter)
+        stub_ldap_adapter_nested_groups(group3_entry.dn, [], adapter)
+
+        expect(group.member_dns).not_to include('cn=ldap_group1,ou=groups,dc=example,dc=com')
+        expect(group.member_dns).not_to include('uid=foo,ou=users,dc=other,dc=com')
+        expect(group.member_dns).to include('uid=bar,ou=users,dc=example , dc=com')
+      end
     end
   end
 end
diff --git a/spec/support/ee/ldap_helpers.rb b/spec/support/ee/ldap_helpers.rb
index 590a63bd0440ac6cf2b97ebd2fbe23fc747307dc..4cec6841af2239118817931a96a8de1dcb17cc5e 100644
--- a/spec/support/ee/ldap_helpers.rb
+++ b/spec/support/ee/ldap_helpers.rb
@@ -46,7 +46,8 @@ def ldap_group_entry(
       members,
       cn: 'ldap_group1',
       objectclass: 'groupOfNames',
-      member_attr: 'uniqueMember'
+      member_attr: 'uniqueMember',
+      member_of: nil
     )
       entry = Net::LDAP::Entry.from_single_ldif_string(<<-EOS.strip_heredoc)
         dn: cn=#{cn},ou=groups,dc=example,dc=com
@@ -56,9 +57,70 @@ def ldap_group_entry(
         objectclass: #{objectclass}
       EOS
 
+      entry['memberOf'] = member_of if member_of
       members = [members].flatten
       entry[member_attr] = members if members.any?
       entry
     end
+
+    # To simulate Active Directory ranged member retrieval. Create an LDAP
+    # group entry with any number of members in a given range. A '*' signifies
+    # the end of the 'pages' has been reached.
+    #
+    # Example:
+    #   ldap_group_entry_with_member_range(
+    #     [ 'user1', 'user2' ],
+    #     cn: 'my_group',
+    #     range_start: '0',
+    #     range_end: '*'
+    #   )
+    def ldap_group_entry_with_member_range(
+      members_in_range,
+      cn: 'ldap_group1',
+      range_start: '0',
+      range_end: '*'
+    )
+      entry = Net::LDAP::Entry.from_single_ldif_string(<<-EOS.strip_heredoc)
+        dn: cn=#{cn},ou=groups,dc=example,dc=com
+        cn: #{cn}
+        description: LDAP Group #{cn}
+      EOS
+
+      members_in_range = [members_in_range].flatten
+      entry["member;range=#{range_start}-#{range_end}"] = members_in_range
+      entry
+    end
+
+    # Stub Active Directory range member retrieval.
+    #
+    # Example:
+    #  adapter = ::Gitlab::LDAP::Adapter.new('ldapmain', double(:ldap))
+    #  group_entry_page1 = ldap_group_entry_with_member_range(
+    #    [user_dn('user1'), user_dn('user2'), user_dn('user3')],
+    #    range_start: '0',
+    #    range_end: '2'
+    #  )
+    #  group_entry_page2 = ldap_group_entry_with_member_range(
+    #    [user_dn('user4'), user_dn('user5'), user_dn('user6')],
+    #    range_start: '3',
+    #    range_end: '*'
+    #  )
+    #  group = EE::Gitlab::LDAP::Group.new(group_entry_page1, adapter)
+    #
+    #  stub_ldap_adapter_group_members_in_range(group_entry_page2, adapter, range_start: '3')
+    def stub_ldap_adapter_group_members_in_range(
+      entry,
+      adapter = ldap_adapter,
+      range_start: '0'
+    )
+      allow(adapter).to receive(:group_members_in_range)
+        .with(entry.dn, range_start.to_i).and_return(entry)
+    end
+
+    def stub_ldap_adapter_nested_groups(parent_dn, entries = [], adapter = ldap_adapter)
+      groups = entries.map { |entry| EE::Gitlab::LDAP::Group.new(entry, adapter) }
+
+      allow(adapter).to receive(:nested_groups).with(parent_dn).and_return(groups)
+    end
   end
 end