diff --git a/cmds/installd/InstalldNativeService.cpp b/cmds/installd/InstalldNativeService.cpp
index 49a3b23..25dbe98 100644
--- a/cmds/installd/InstalldNativeService.cpp
+++ b/cmds/installd/InstalldNativeService.cpp
@@ -1089,10 +1089,13 @@
 
     ALOGV("unlink %s\n", dex_path);
     if (unlink(dex_path) < 0) {
-        return error(StringPrintf("Failed to unlink %s", dex_path));
-    } else {
-        return ok();
+        // It's ok if we don't have a dalvik cache path. Report error only when the path exists
+        // but could not be unlinked.
+        if (errno != ENOENT) {
+            return error(StringPrintf("Failed to unlink %s", dex_path));
+        }
     }
+    return ok();
 }
 
 struct stats {
diff --git a/cmds/installd/tests/installd_service_test.cpp b/cmds/installd/tests/installd_service_test.cpp
index 4a1f333..34818f6 100644
--- a/cmds/installd/tests/installd_service_test.cpp
+++ b/cmds/installd/tests/installd_service_test.cpp
@@ -54,10 +54,12 @@
     return false;
 }
 
-bool create_cache_path(char path[PKG_PATH_MAX] ATTRIBUTE_UNUSED,
-        const char *src ATTRIBUTE_UNUSED,
-        const char *instruction_set ATTRIBUTE_UNUSED) {
-    return false;
+bool create_cache_path(char path[PKG_PATH_MAX],
+        const char *src,
+        const char *instruction_set) {
+    // Not really a valid path but it's good enough for testing.
+    sprintf(path,"/data/dalvik-cache/%s/%s", instruction_set, src);
+    return true;
 }
 
 static void mkdir(const char* path, uid_t owner, gid_t group, mode_t mode) {
@@ -151,5 +153,13 @@
     EXPECT_EQ(10000, stat_gid("com.example/bar/file"));
 }
 
+TEST_F(ServiceTest, RmDexNoDalvikCache) {
+    LOG(INFO) << "RmDexNoDalvikCache";
+
+    // Try to remove a non existing dalvik cache dex. The call should be
+    // successful because there's nothing to remove.
+    EXPECT_TRUE(service->rmdex("com.example", "arm").isOk());
+}
+
 }  // namespace installd
 }  // namespace android