diff --git a/src/main/java/com/google/dexmaker/AppDataDirGuesser.java b/src/main/java/com/google/dexmaker/AppDataDirGuesser.java
index 2492ea0..3252a1c 100644
--- a/src/main/java/com/google/dexmaker/AppDataDirGuesser.java
+++ b/src/main/java/com/google/dexmaker/AppDataDirGuesser.java
@@ -71,14 +71,25 @@
             if (dash != -1) {
                 end = dash;
             }
-            File file = new File("/data/data/" + potential.substring(start, end) + "/cache");
-            if (isWriteableDirectory(file)) {
-                results.add(file);
+            String packageName = potential.substring(start, end);
+            File dataDir = new File("/data/data/" + packageName);
+            if (isWriteableDirectory(dataDir)) {
+                File cacheDir = new File(dataDir, "cache");
+                // The cache directory might not exist -- create if necessary
+                if (fileOrDirExists(cacheDir) || cacheDir.mkdir()) {
+                    if (isWriteableDirectory(cacheDir)) {
+                        results.add(cacheDir);
+                    }
+                }
             }
         }
         return results.toArray(new File[results.size()]);
     }
 
+    boolean fileOrDirExists(File file) {
+        return file.exists();
+    }
+
     boolean isWriteableDirectory(File file) {
         return file.isDirectory() && file.canWrite();
     }
diff --git a/src/test/java/com/google/dexmaker/AppDataDirGuesserTest.java b/src/test/java/com/google/dexmaker/AppDataDirGuesserTest.java
index 5c92f34..36ac383 100644
--- a/src/test/java/com/google/dexmaker/AppDataDirGuesserTest.java
+++ b/src/test/java/com/google/dexmaker/AppDataDirGuesserTest.java
@@ -80,6 +80,10 @@
                     public boolean isWriteableDirectory(File file) {
                         return !notWriteable.contains(file.getAbsolutePath());
                     }
+                    @Override
+                    boolean fileOrDirExists(File file) {
+                        return true;
+                    }
                 };
                 File[] results = guesser.guessPath(path);
                 assertNotNull("Null results for " + path, results);