diff --git a/github-oauth/src/main/java/com/googlesource/gerrit/plugins/github/oauth/IdentifiedUserGitHubLoginProvider.java b/github-oauth/src/main/java/com/googlesource/gerrit/plugins/github/oauth/IdentifiedUserGitHubLoginProvider.java
index 4ea4494..c5c7161 100644
--- a/github-oauth/src/main/java/com/googlesource/gerrit/plugins/github/oauth/IdentifiedUserGitHubLoginProvider.java
+++ b/github-oauth/src/main/java/com/googlesource/gerrit/plugins/github/oauth/IdentifiedUserGitHubLoginProvider.java
@@ -15,7 +15,6 @@
 package com.googlesource.gerrit.plugins.github.oauth;
 
 import com.google.gerrit.common.Nullable;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.server.IdentifiedUser;
 import com.google.gerrit.server.account.AccountCache;
 import com.google.gerrit.server.account.AccountState;
@@ -34,7 +33,7 @@
   private static final Logger log =
       LoggerFactory.getLogger(IdentifiedUserGitHubLoginProvider.class);
   public static final String EXTERNAL_ID_PREFIX =
-      AccountExternalId.SCHEME_EXTERNAL + OAuthWebFilter.GITHUB_EXT_ID;
+      ExternalId.SCHEME_EXTERNAL + ":" + OAuthWebFilter.GITHUB_EXT_ID;
 
   private final Provider<IdentifiedUser> userProvider;
   private final GitHubOAuthConfig config;
@@ -80,7 +79,7 @@
     AccountState account = accountCache.getByUsername(username);
     Collection<ExternalId> externalIds = account.getExternalIds();
     for (ExternalId accountExternalId : externalIds) {
-      String key = accountExternalId.asAccountExternalId().getKey().get();
+      String key = accountExternalId.key().get();
       if (key.startsWith(EXTERNAL_ID_PREFIX)) {
         return new AccessToken(key.substring(EXTERNAL_ID_PREFIX.length()));
       }
diff --git a/github-plugin/src/main/java/com/google/gerrit/server/account/AccountImporter.java b/github-plugin/src/main/java/com/google/gerrit/server/account/AccountImporter.java
index ef9ba3c..dd8f712 100644
--- a/github-plugin/src/main/java/com/google/gerrit/server/account/AccountImporter.java
+++ b/github-plugin/src/main/java/com/google/gerrit/server/account/AccountImporter.java
@@ -23,54 +23,48 @@
 import com.google.gerrit.extensions.restapi.UnprocessableEntityException;
 import com.google.gerrit.reviewdb.client.Account;
 import com.google.gerrit.reviewdb.client.Account.Id;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
-import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.account.CreateAccount.Factory;
+import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIdsUpdate;
 import com.google.gwtorm.server.OrmException;
 import com.google.inject.Inject;
-import com.google.inject.Provider;
 import java.io.IOException;
-import java.util.Arrays;
 import org.apache.http.HttpStatus;
 import org.eclipse.jgit.errors.ConfigInvalidException;
 
 public class AccountImporter {
   private final Factory createAccountFactory;
-  private final Provider<ReviewDb> schema;
+  private final ExternalIdsUpdate.Server externalIdsUpdateServer;
 
   @Inject
   public AccountImporter(
-      final CreateAccount.Factory createAccountFactory, final Provider<ReviewDb> schema) {
+      final CreateAccount.Factory createAccountFactory,
+      ExternalIdsUpdate.Server externalIdsUpdateServer) {
     this.createAccountFactory = createAccountFactory;
-    this.schema = schema;
+    this.externalIdsUpdateServer = externalIdsUpdateServer;
   }
 
   public Account.Id importAccount(String login, String name, String email)
       throws IOException, BadRequestException, ResourceConflictException,
           UnprocessableEntityException, OrmException, ConfigInvalidException {
-    try (ReviewDb db = schema.get()) {
-      CreateAccount createAccount = createAccountFactory.create(login);
-      AccountInput accountInput = new AccountInput();
-      accountInput.email = email;
-      accountInput.username = login;
-      accountInput.name = MoreObjects.firstNonNull(name, login);
-      Response<AccountInfo> accountResponse =
-          createAccount.apply(TopLevelResource.INSTANCE, accountInput);
-      if (accountResponse.statusCode() != HttpStatus.SC_CREATED) {
-        throw new IOException(
-            "Cannot import GitHub account "
-                + login
-                + ": HTTP Status "
-                + accountResponse.statusCode());
-      }
-      Id accountId = new Account.Id(accountResponse.value()._accountId.intValue());
-      db.accountExternalIds()
-          .insert(
-              Arrays.asList(
-                  new AccountExternalId(
-                      accountId,
-                      new AccountExternalId.Key(AccountExternalId.SCHEME_GERRIT, login))));
-      return accountId;
+    CreateAccount createAccount = createAccountFactory.create(login);
+    AccountInput accountInput = new AccountInput();
+    accountInput.email = email;
+    accountInput.username = login;
+    accountInput.name = MoreObjects.firstNonNull(name, login);
+    Response<AccountInfo> accountResponse =
+        createAccount.apply(TopLevelResource.INSTANCE, accountInput);
+    if (accountResponse.statusCode() != HttpStatus.SC_CREATED) {
+      throw new IOException(
+          "Cannot import GitHub account "
+              + login
+              + ": HTTP Status "
+              + accountResponse.statusCode());
     }
+    Id accountId = new Account.Id(accountResponse.value()._accountId.intValue());
+    externalIdsUpdateServer
+        .create()
+        .insert(ExternalId.create(ExternalId.SCHEME_GERRIT, login, accountId));
+    return accountId;
   }
 }
diff --git a/github-plugin/src/main/java/com/googlesource/gerrit/plugins/github/GitHubOAuthServiceProvider.java b/github-plugin/src/main/java/com/googlesource/gerrit/plugins/github/GitHubOAuthServiceProvider.java
index 7a52be1..7ee4dbf 100644
--- a/github-plugin/src/main/java/com/googlesource/gerrit/plugins/github/GitHubOAuthServiceProvider.java
+++ b/github-plugin/src/main/java/com/googlesource/gerrit/plugins/github/GitHubOAuthServiceProvider.java
@@ -19,7 +19,7 @@
 import com.google.gerrit.extensions.auth.oauth.OAuthToken;
 import com.google.gerrit.extensions.auth.oauth.OAuthUserInfo;
 import com.google.gerrit.extensions.auth.oauth.OAuthVerifier;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
+import com.google.gerrit.server.account.externalids.ExternalId;
 import com.google.inject.Inject;
 import com.googlesource.gerrit.plugins.github.oauth.GitHubOAuthConfig;
 import com.googlesource.gerrit.plugins.github.oauth.OAuthProtocol;
@@ -65,7 +65,7 @@
     GHMyself myself = hub.getMyself();
     String login = myself.getLogin();
     return new OAuthUserInfo(
-        AccountExternalId.SCHEME_GERRIT + login, login, myself.getEmail(), myself.getName(), null);
+        ExternalId.SCHEME_GERRIT + login, login, myself.getEmail(), myself.getName(), null);
   }
 
   @Override
diff --git a/github-plugin/src/main/java/com/googlesource/gerrit/plugins/github/filters/GitHubOAuthFilter.java b/github-plugin/src/main/java/com/googlesource/gerrit/plugins/github/filters/GitHubOAuthFilter.java
index 5316d13..60f3132 100644
--- a/github-plugin/src/main/java/com/googlesource/gerrit/plugins/github/filters/GitHubOAuthFilter.java
+++ b/github-plugin/src/main/java/com/googlesource/gerrit/plugins/github/filters/GitHubOAuthFilter.java
@@ -15,7 +15,6 @@
 
 import com.google.common.base.Predicate;
 import com.google.common.collect.Collections2;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.server.CurrentUser;
 import com.google.gerrit.server.IdentifiedUser;
 import com.google.gerrit.server.account.AccountCache;
@@ -71,17 +70,21 @@
     if (!hubLogin.isLoggedIn()
         && !OAuthFilter.skipOAuth((HttpServletRequest) request)
         && user.isIdentifiedUser()) {
-      AccountExternalId gitHubExtId = getGitHubExternalId(user);
+      ExternalId gitHubExtId = getGitHubExternalId(user);
 
       String oauthToken =
-          gitHubExtId.getSchemeRest().substring(OAuthWebFilter.GITHUB_EXT_ID.length());
+          gitHubExtId
+              .key()
+              .get()
+              .substring(
+                  ExternalId.SCHEME_EXTERNAL.length() + OAuthWebFilter.GITHUB_EXT_ID.length() + 1);
       hubLogin.login(new AccessToken(oauthToken));
     }
 
     chain.doFilter(request, response);
   }
 
-  private AccountExternalId getGitHubExternalId(CurrentUser user) {
+  private ExternalId getGitHubExternalId(CurrentUser user) {
     Collection<ExternalId> accountExtIds =
         accountCache.get(((IdentifiedUser) user).getAccountId()).getExternalIds();
     Collection<ExternalId> gitHubExtId =
@@ -101,7 +104,7 @@
       throw new IllegalStateException(
           "Current Gerrit user " + user.getUserName() + " has no GitHub OAuth external ID");
     }
-    return gitHubExtId.iterator().next().asAccountExternalId();
+    return gitHubExtId.iterator().next();
   }
 
   @Override
diff --git a/github-plugin/src/main/java/com/googlesource/gerrit/plugins/github/git/PullRequestImportJob.java b/github-plugin/src/main/java/com/googlesource/gerrit/plugins/github/git/PullRequestImportJob.java
index f0bf9df..646737e 100644
--- a/github-plugin/src/main/java/com/googlesource/gerrit/plugins/github/git/PullRequestImportJob.java
+++ b/github-plugin/src/main/java/com/googlesource/gerrit/plugins/github/git/PullRequestImportJob.java
@@ -20,13 +20,13 @@
 import com.google.gerrit.extensions.restapi.ResourceConflictException;
 import com.google.gerrit.extensions.restapi.UnprocessableEntityException;
 import com.google.gerrit.reviewdb.client.Account;
-import com.google.gerrit.reviewdb.client.AccountExternalId;
 import com.google.gerrit.reviewdb.client.Change.Id;
 import com.google.gerrit.reviewdb.client.Project;
 import com.google.gerrit.reviewdb.client.Project.NameKey;
-import com.google.gerrit.reviewdb.server.AccountExternalIdAccess;
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.account.AccountImporter;
+import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIds;
 import com.google.gerrit.server.git.GitRepositoryManager;
 import com.google.gerrit.server.project.ProjectCache;
 import com.google.gerrit.server.project.ProjectState;
@@ -39,6 +39,7 @@
 import com.googlesource.gerrit.plugins.github.oauth.ScopedProvider;
 import java.io.IOException;
 import java.util.List;
+import java.util.Optional;
 import org.eclipse.jgit.api.FetchCommand;
 import org.eclipse.jgit.api.Git;
 import org.eclipse.jgit.api.errors.GitAPIException;
@@ -82,6 +83,7 @@
   private final int prId;
   private final GitRepositoryManager repoMgr;
   private final int jobIndex;
+  private final ExternalIds externalIds;
   private PullRequestCreateChange createChange;
   private Project project;
   private GitJobStatus status;
@@ -98,6 +100,7 @@
       AccountImporter accountImporter,
       GitHubRepository.Factory gitHubRepoFactory,
       ScopedProvider<GitHubLogin> ghLoginProvider,
+      ExternalIds externalIds,
       @Assisted("index") int jobIndex,
       @Assisted("organisation") String organisation,
       @Assisted("name") String repoName,
@@ -114,6 +117,7 @@
     this.status = new GitJobStatus(jobIndex);
     this.schema = schema;
     this.accountImporter = accountImporter;
+    this.externalIds = externalIds;
   }
 
   private Project fetchGerritProject(
@@ -212,14 +216,20 @@
       ReviewDb db, String login, String name, String email)
       throws OrmException, BadRequestException, ResourceConflictException,
           UnprocessableEntityException, IOException, ConfigInvalidException {
-    AccountExternalId.Key userExtKey =
-        new AccountExternalId.Key(AccountExternalId.SCHEME_USERNAME, login);
-    AccountExternalIdAccess gerritExtIds = db.accountExternalIds();
-    AccountExternalId userExtId = gerritExtIds.get(userExtKey);
-    if (userExtId == null) {
-      return accountImporter.importAccount(login, name, email);
+    Optional<ExternalId> gerritId = externalIdByScheme(ExternalId.SCHEME_GERRIT, login);
+    if (gerritId.isPresent()) {
+      return gerritId.get().accountId();
     }
-    return userExtId.getAccountId();
+    return accountImporter.importAccount(login, name, email);
+  }
+
+  private Optional<ExternalId> externalIdByScheme(String scheme, String id) {
+    try {
+      return Optional.ofNullable(externalIds.get(ExternalId.Key.create(scheme, id)));
+    } catch (IOException | ConfigInvalidException e) {
+      LOG.error("Unable to get external id for " + scheme + ":" + id, e);
+      return Optional.empty();
+    }
   }
 
   private String getChangeMessage(GHPullRequest pr) {