Unable to execute dex: method ID not in [0, 0xffff]: 65536

Update 3 (11/3/2014)
Google finally released official description.

Update 2 (10/31/2014)
Gradle plugin v0.14.0 for Android adds support for multi-dex. To enable, you just have to declare it in build.gradle:

android {
   defaultConfig {
      ...
      multiDexEnabled  true
   }
}

If your application supports Android prior to 5.0 (that is, if your minSdkVersion is 20 or below) you also have to dynamically patch the application ClassLoader, so it will be able to load classes from secondary dexes. Fortunately, there's a library that does that for you. Add it to your app's dependencies:

dependencies {
  ...
  compile 'com.android.support:multidex:1.0.0'
} 

You need to call the ClassLoader patch code as soon as possible. MultiDexApplication class's documentation suggests three ways to do that (pick one of them, one that's most convenient for you):

1 - Declare MultiDexApplication class as the application in your AndroidManifest.xml:

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="com.example.android.multidex.myapplication">
    <application
        ...
        android:name="android.support.multidex.MultiDexApplication">
        ...
    </application>
</manifest>

2 - Have your Application class extend MultiDexApplication class:

public class MyApplication extends MultiDexApplication { .. }

3 - Call MultiDex#install from your Application#attachBaseContext method:

public class MyApplication {
    protected void attachBaseContext(Context base) {
        super.attachBaseContext(base);
        MultiDex.install(this);
        ....
    }
    ....
}

Update 1 (10/17/2014):
As anticipated, multidex support is shipped in revision 21 of Android Support Library. You can find the android-support-multidex.jar in /sdk/extras/android/support/multidex/library/libs folder.

Multi-dex support solves this problem. dx 1.8 already allows generating several dex files.
Android L will support multi-dex natively, and next revision of support library is going to cover older releases back to API 4.

It was stated in this Android Developers Backstage podcast episode by Anwar Ghuloum. I've posted a transcript (and general multi-dex explanation) of the relevant part.

As already stated, you have too many methods (more than 65k) in your project and libs.

Prevent the Problem: Reduce the number of methods with Play Services 6.5+ and support-v4 24.2+

Since often the Google Play services is one of the main suspects in "wasting" methods with its 20k+ methods. Google Play services version 6.5 or later, it is possible for you to include Google Play services in your application using a number of smaller client libraries. For example, if you only need GCM and maps you can choose to use these dependencies only:

dependencies {
    compile 'com.google.android.gms:play-services-base:6.5.+'
    compile 'com.google.android.gms:play-services-maps:6.5.+'
}

The full list of sub libraries and it's responsibilities can be found in the official google doc.

Update: Since Support Library v4 v24.2.0 it was split up into the following modules:

support-compat, support-core-utils, support-core-ui, support-media-compat and support-fragment

dependencies {
    compile 'com.android.support:support-fragment:24.2.+'
}

Do note however, if you use support-fragment, it will have dependencies to all the other modules (ie. if you use android.support.v4.app.Fragment there is no benefit)

See here the official release notes for support-v4 lib

Enable MultiDexing

Since Lollipop (aka build tools 21+) it is very easy to handle. The approach is to work around the 65k methods per dex file problem to create multiple dex files for your app. Add the following to your gradle build file (this is taken from the official google doc on applications with more than 65k methods):

android {
    compileSdkVersion 21
    buildToolsVersion "21.1.0"

    defaultConfig {
        ...
        // Enabling multidex support.
        multiDexEnabled true
    }
    ...
}

dependencies {
  compile 'com.android.support:multidex:1.0.1'
}

The second step is to either prepare your Application class or if you don't extend Application use the MultiDexApplication in your Android Manifest:

Either add this to your Application.java

@Override
  protected void attachBaseContext(Context base) {
    super.attachBaseContext(base);
    MultiDex.install(this);
  }

or use the provided application from the mutlidex lib

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="com.example.android.myapplication">
    <application
        ...
        android:name="android.support.multidex.MultiDexApplication">
        ...
    </application>
</manifest>

Prevent OutOfMemory with MultiDex

As further tip, if you run into OutOfMemory exceptions during the build phase you could enlarge the heap with

android {
    ...
    dexOptions {
        javaMaxHeapSize "4g"
    }
}

which would set the heap to 4 gigabytes.

See this question for more detail on the dex heap memory issue.

Analyze the source of the Problem

To analyze the source of the methods the gradle plugin https://github.com/KeepSafe/dexcount-gradle-plugin can help in combination with the dependency tree provided by gradle with e.g.

.\gradlew app:dependencies

See this answer and question for more information on method count in android

Your project is too large. You have too many methods. There can only be 65536 methods per application. see here https://code.google.com/p/android/issues/detail?id=7147#c6

The below code helps, if you use Gradle. Allows you to easily remove unneeded Google services (presuming you're using them) to get back below the 65k threshold. All credit to this post: https://gist.github.com/dmarcato/d7c91b94214acd936e42

Edit 2014-10-22: There's been a lot of interesting discussion on the gist referenced above. TLDR? look at this one: https://gist.github.com/Takhion/10a37046b9e6d259bb31

Paste this code at the bottom of your build.gradle file and adjust the list of google services you do not need:

def toCamelCase(String string) {
    String result = ""
    string.findAll("[^\\W]+") { String word ->
        result += word.capitalize()
    }
    return result
}

afterEvaluate { project ->
    Configuration runtimeConfiguration = project.configurations.getByName('compile')
    ResolutionResult resolution = runtimeConfiguration.incoming.resolutionResult
    // Forces resolve of configuration
    ModuleVersionIdentifier module = resolution.getAllComponents().find { it.moduleVersion.name.equals("play-services") }.moduleVersion

    String prepareTaskName = "prepare${toCamelCase("${module.group} ${module.name} ${module.version}")}Library"
    File playServiceRootFolder = project.tasks.find { it.name.equals(prepareTaskName) }.explodedDir

    Task stripPlayServices = project.tasks.create(name: 'stripPlayServices', group: "Strip") {
        inputs.files new File(playServiceRootFolder, "classes.jar")
        outputs.dir playServiceRootFolder
        description 'Strip useless packages from Google Play Services library to avoid reaching dex limit'

        doLast {
            copy {
                from(file(new File(playServiceRootFolder, "classes.jar")))
                into(file(playServiceRootFolder))
                rename { fileName ->
                    fileName = "classes_orig.jar"
                }
            }
            tasks.create(name: "stripPlayServices" + module.version, type: Jar) {
                destinationDir = playServiceRootFolder
                archiveName = "classes.jar"
                from(zipTree(new File(playServiceRootFolder, "classes_orig.jar"))) {
                    exclude "com/google/ads/**"
                    exclude "com/google/android/gms/analytics/**"
                    exclude "com/google/android/gms/games/**"
                    exclude "com/google/android/gms/plus/**"
                    exclude "com/google/android/gms/drive/**"
                    exclude "com/google/android/gms/ads/**"
                }
            }.execute()
            delete file(new File(playServiceRootFolder, "classes_orig.jar"))
        }
    }

    project.tasks.findAll { it.name.startsWith('prepare') && it.name.endsWith('Dependencies') }.each { Task task ->
        task.dependsOn stripPlayServices
    }
}

I've shared a sample project which solve this problem using custom_rules.xml build script and a few lines of code.

I used it on my own project and it is runs flawless on 1M+ devices (from android-8 to the latest android-19). Hope it helps.

https://github.com/mmin18/Dex65536