Mobile permission decisions are often studied at the moment a permission request appears. However, our study shows that users’ choices are shaped much earlier, across a multi-stage journey that begins with app-need recognition and unfolds through app discovery, exploration, selection, installation, and first use. Drawing on interviews with 19 U.S. Android users, we map this process and identify four archetypal journeys that explain how early cues, such as discovery sources, app type, and social trust, shape later permission behavior. These insights align with theoretical models like Privacy Calculus, showing how users weigh perceived benefits and risks at each step, and complement Contextual Integrity theory, explaining how social norms and information flows shape expectations and constrain privacy agency across steps. We contribute an empirically grounded framework that clarifies why permission outcomes vary across contexts. Our results reframe mobile privacy as a sequential, path-dependent process, offering implications for future design and research.