Signaling trough cytoplasmic or nuclear action of p53 is a major response mechanism to cellular stresses. While p53 protein levels have been shown to increase upon nutrient stresses such as starvation, the exact signaling cascade in this context remains elusive. Here, we show in a human hepatoma cell line that nutrient withdrawal leads to robust nuclear p53 stabilization and utilize various complementary omics approaches to dissect upstream and downstream networks in the response to starvation. Using the affinity purification mass spectrometry (MS) method BioID, we determine the cytoplasmic p53 interaction network within the immediate-early starvation response and show that p53 is dissociated from several metabolic enzymes and the kinase PAK2. Direct binding of p53 DNA-binding domain and N-terminal PAK2 was confirmed with nuclear magnetic resonance (NMR) interaction studies. Furthermore, rapid immunoprecipitation MS of endogenous proteins (RIME) uncovered the nuclear interactome under prolonged starvation, where we confirmed the novel p53 interactors SORBS1, involved in insulin signaling, and UGP2, a key enzyme of glycogen synthesis. Finally, transcriptomics after p53 re-expression on a CRISPR/Cas9 knock out background revealed a distinct starvation-specific transcriptome response and suggested novel nutrient-dependent p53 target genes. Together, our complementary approaches delineate several nodes of the p53 signaling cascade in response to starvation, shedding new light on the mechanisms of p53 as a nutrient stress sensor and regulator of specific transcriptional output. Given the central role of p53 in cancer biology and the beneficial effects of fasting in cancer treatment, the identified interaction partners and networks could pinpoint novel pharmacologic targets to fine-tune p53 activity.