Update Aug 2017

As of version 11.2.0 Firebase and Google Play services dependencies are available via Google's Maven Repo. You no longer need to use the Android SDK manager to import these dependencies.

In your root build.gradle file add the repo:

allprojects {
  repositories {
    // ...
    maven { url "https://maven.google.com" }
  }
}

If you are using gradle 4.0 or higher you can replace maven { url "https://maven.google.com" } with just google().

---

The 9.0.0 version of Firebase was built using Google Play services 9.0 and is now available under the new packaging com.google.firebase:*

See Release Notes for Google Play services 9.0 https://developers.google.com/android/guides/releases#may_2016_-_v90

New versions of packages Google Play Services (rev 30) and Google Repository (rev 26) were just released in the SDK manager so it's likely you just need to update.

---

Downloading Google Play Services and Google Repository

From Android Studio:

1. Click Tools > Android > SDK Manager.
2. Click into the SDK Tools tab.
3. Select and install Google Play Services (rev 30) and Google Repository (rev 26). See the image below.
4. Sync and Build your project.

---

From IntelliJ IDEA:

As of April 2017, the latest versions of Google Play Services and Repository are listed below.

1. Click Tools > Android > SDK Manager.
2. Under the Packages panel, Look for the Extras.
3. Select and install Google Play Services (rev 39) and Google Repository (rev 46). See the image below.
4. Perform a gradle project sync and Build your project.