The inhibitor of the nuclear factor-κB (IκB) kinase (IKK) complex is a key regulator of the canonical NF-κB signalling cascade and is crucial for fundamental cellular functions, including stress and immune responses. The majority of IKK complex functions are attributed to NF-κB activation; however, there is increasing evidence for NF-κB pathway-independent signalling. Here we combine quantitative mass spectrometry with random forest bioinformatics to dissect the TNF-α-IKKβ-induced phosphoproteome in MCF-7 breast cancer cells. In total, we identify over 20,000 phosphorylation sites, of which ∼1% are regulated up on TNF-α stimulation. We identify various potential novel IKKβ substrates including kinases and regulators of cellular trafficking. Moreover, we show that one of the candidates, AEG-1/MTDH/LYRIC, is directly phosphorylated by IKKβ on serine 298. We provide evidence that IKKβ-mediated AEG-1 phosphorylation is essential for IκBα degradation as well as NF-κB-dependent gene expression and cell proliferation, which correlate with cancer patient survival in vivo.