The identification of the regulatory proteins that control DNA transcription as well as RNA stability and translation represents a key step in the comprehension of gene expression regulation. Those proteins can be purified by DNA- or RNA-affinity chromatography, followed by identification by mass spectrometry. Although very simple in the concept, this represents a real technological challenge due to the low abundance of regulatory proteins compared to the highly abundant proteins binding to nucleic acids in a nonsequence-specific manner. Here we review the different strategies that have been set up to reach this purpose, discussing the key parameters that should be considered to increase the chances of success. Typically, two categories of biological questions can be distinguished: the identification of proteins that specifically interact with a precisely defined binding site, mostly addressed by quantitative mass spectrometry, and the identification in a non-comparative manner of the protein complexes recruited by a poorly characterized long regulatory region of nucleic acids. Finally, beside the numerous studies devoted to in vitro-assembled nucleic acid-protein complexes, the scarce data reported on proteomic analyses of in vivo-assembled complexes are described, with a special emphasis on the associated challenges.