With PVMOdex, we introduce a new virtualization-based obfuscator for Android that recompiles a method-level selection of the original app. Recompiled methods get transformed into a custom bytecode for a randomly generated interpreter. The random interpreter is injected into the original APK along with other protection mechanisms that thwart reverse engineering and tampering, such as anti-debugging, rooting, and hooking. Removing these extra safeguards requires the analysis of the virtualization layer, meaning an attacker would have to learn the randomly generated bytecode language first. To prove the applicability of our approach, we applied PVMOdex to over 100 of the most downloaded apps from theGoogle Play Store, obfuscating 9,914,463 methods. We examine the worst-case scenario of the overhead our obfuscator could introduce by obfuscating not only relevant methods within an app, such as license checks but all developer generated source code, including even UI interactions. At this full obfuscation, the CPU usage of apps in our test-set is on average doubled, and the average memory usage increases by only 32.50%. And while the runtime of fully obfuscated apps is affected by virtualization, our approach allows fora fine-grained method-level selection of obfuscated code, yielding much lower overheads in the average and best-case scenarios when only a fraction of the original source code is obfuscated.