diff --git a/db/migrate/20160413213231_clean_ldap_extern_uids.rb b/db/migrate/20160413213231_clean_ldap_extern_uids.rb
new file mode 100644
index 0000000000000000000000000000000000000000..78aee310fd741b4fe599f343053ddce2a62adb52
--- /dev/null
+++ b/db/migrate/20160413213231_clean_ldap_extern_uids.rb
@@ -0,0 +1,30 @@
+require 'net/ldap/dn'
+
+class CleanLdapExternUids < ActiveRecord::Migration
+  def up
+    select_all("SELECT id, extern_uid FROM identities WHERE identities.provider LIKE 'ldap%'").each do |ldap_identity|
+      id = ldap_identity['id']
+      extern_uid_was = ldap_identity['extern_uid'].clone
+      extern_uid = clean_dn(ldap_identity['extern_uid'])
+
+      if extern_uid != extern_uid_was
+        execute("UPDATE identities SET extern_uid = '#{quote_string(extern_uid)}' WHERE id = #{id}")
+      end
+    end
+  end
+
+  def down
+    # There's no going back! Shouldn't be a big deal.
+  end
+
+  private
+
+  def clean_dn(dn)
+    clean_pairs = []
+    Net::LDAP::DN.new(dn).each_pair do |k,v|
+      # No need to escape the value. `each_pair` already escapes for us.
+      clean_pairs << "#{k}=#{v}"
+    end
+    Net::LDAP::DN.new(clean_pairs.join(',')).to_s
+  end
+end
diff --git a/db/schema.rb b/db/schema.rb
index 199f3e0249fae1b02f5e673e9cbf5b8f51984ef3..70755f816ef935d12659b3f7ed73469112a455cf 100644
--- a/db/schema.rb
+++ b/db/schema.rb
@@ -11,7 +11,7 @@
 #
 # It's strongly recommended that you check this file into your version control system.
 
-ActiveRecord::Schema.define(version: 20160331223143) do
+ActiveRecord::Schema.define(version: 20160413213231) do
 
   # These are extensions that must be enabled in order to support this database
   enable_extension "plpgsql"
diff --git a/lib/gitlab/ldap/group_sync.rb b/lib/gitlab/ldap/group_sync.rb
index 38207d7f077a3eff8d41beafac8c5566f09cbc55..26e72c3ac659a4da3391ac417ad2a460b1d06146 100644
--- a/lib/gitlab/ldap/group_sync.rb
+++ b/lib/gitlab/ldap/group_sync.rb
@@ -168,6 +168,10 @@ def ldap_group_member_dns(ldap_group_cn)
           member_dns = members.map { |uid| dn_for_uid(uid) }.compact
         end
 
+        # Sanitize the DNs to avoid problems when looking up identities later.
+        # See gitlab-ee#365
+        clean_dns!(member_dns)
+
         logger.debug { "Members in '#{ldap_group.name}' LDAP group: #{member_dns}" }
 
         member_dns
@@ -192,6 +196,10 @@ def member_uid_to_dn(uid)
         end
       end
 
+      def clean_dns!(dns)
+        dns.map! { |dn| Gitlab::LDAP::Person.clean_dn(dn) }
+      end
+
       def update_identity(dn, uid)
         identity =
           Identity.find_by(provider: provider, extern_uid: dn)
diff --git a/lib/gitlab/ldap/person.rb b/lib/gitlab/ldap/person.rb
index 4cdaf30cd9ce8308fdf0089203136e7cf66608e3..3cb2a908c0d19e9977aee7ea8587b3a70b375dcf 100644
--- a/lib/gitlab/ldap/person.rb
+++ b/lib/gitlab/ldap/person.rb
@@ -1,3 +1,5 @@
+require 'net/ldap/dn'
+
 module Gitlab
   module LDAP
     class Person
@@ -21,6 +23,17 @@ def self.disabled_via_active_directory?(dn, adapter)
         adapter.dn_matches_filter?(dn, AD_USER_DISABLED)
       end
 
+      # Sometimes LDAP contains dirty DNs. `Net::LDAP::DN.each_pair` does some
+      # magical clean up and then we put it all back together. See gitlab-ee#365
+      def self.clean_dn(dn)
+        clean_pairs = []
+        Net::LDAP::DN.new(dn).each_pair do |k,v|
+          # No need to escape the value. `each_pair` already escapes for us.
+          clean_pairs << "#{k}=#{v}"
+        end
+        Net::LDAP::DN.new(clean_pairs.join(',')).to_s
+      end
+
       def initialize(entry, provider)
         Rails.logger.debug { "Instantiating #{self.class.name} with LDIF:\n#{entry.to_ldif}" }
         @entry = entry
diff --git a/lib/gitlab/ldap/user.rb b/lib/gitlab/ldap/user.rb
index b84c81f1a6cd098954e2f7fc126b1f34b317191f..c127291e72c978385cd516672c8e7368393bebb5 100644
--- a/lib/gitlab/ldap/user.rb
+++ b/lib/gitlab/ldap/user.rb
@@ -52,10 +52,11 @@ def update_user_attributes
           identity = gl_user.identities.find { |identity|  identity.provider == auth_hash.provider }
           identity ||= gl_user.identities.build(provider: auth_hash.provider)
 
+          # Store a sanitized DN to avoid data consistency problems later. See gitlab-ee#365
           # For a new identity set extern_uid to the LDAP DN
           # For an existing identity with matching email but changed DN, update the DN.
           # For an existing identity with no change in DN, this line changes nothing.
-          identity.extern_uid = auth_hash.uid
+          identity.extern_uid = Gitlab::LDAP::Person.clean_dn(auth_hash.uid)
         end
 
         gl_user.ldap_email = auth_hash.has_email?
diff --git a/spec/lib/gitlab/ldap/person_spec.rb b/spec/lib/gitlab/ldap/person_spec.rb
index ac5b4dc3acb8687d1568d5e61c3389535382baa8..b51c179d600340a53a53ebb7a4f990cb1adbcc76 100644
--- a/spec/lib/gitlab/ldap/person_spec.rb
+++ b/spec/lib/gitlab/ldap/person_spec.rb
@@ -1,6 +1,19 @@
 require "spec_helper"
 
 describe Gitlab::LDAP::Person do
+  describe '.clean_dn' do
+    it 'strips weird whitespace' do
+      dn = 'uid=johndoe, ou=people , dc=example,dc=com'
+      expect(Gitlab::LDAP::Person.clean_dn(dn)).
+        to eq('uid=johndoe,ou=people,dc=example,dc=com')
+    end
+
+    it 'does not change good DNs' do
+      dn = 'uid=janedoe,ou=people,dc=example,dc=com'
+      expect(Gitlab::LDAP::Person.clean_dn(dn)).
+        to eq('uid=janedoe,ou=people,dc=example,dc=com')
+    end
+  end
 
   describe "#kerberos_principal" do