Current mobile applications (apps) have become increasingly complicated with increasing features that are represented on the graphical user interface associated with application programming interfaces (APIs) to access backend functionality and data. Meanwhile, apps suffer from the “software bloat” in volume. Some app features may be redundant, with respect to those features (from other apps) that the users already desirably and frequently use. However, the current app release model forces users to download and install a full-size installation package rather than optionally choosing only their desired features. Large-size apps can not only increase the local resource consumption, such as CPU, memory, and energy, but also inevitably compromise the user experience, such as the slow load time in the app. In this article, we first conduct an empirical study to characterize the app feature usage when users interact with Android apps, and surprisingly find that users access only a very small subset of app features. Based on these findings, we design a new approach named LegoDroid, which automatically decomposes an Android app for flexible loading and installation, while preserving the expected functionality with a fast and instant app load. With such a method, a slimmer bundle will be downloaded and host the target APIs inside the original app to satisfy users’ requirements. We implement a system for LegoDroid and evaluate it with 1000 real-world Android apps. Compared to the original full-size apps, apps optimized by LegoDroid can substantially improve the load time by reducing the base bundle and feature bundles by 13.06% and 10.93%, respectively, along with the app-package installation size by 44.17%. In addition, we also demonstrate that LegoDroid is quite practical with evolving versions, as it can produce substantial reusable code to alleviate the developers’ efforts when releasing new app versions.