Metabolite-protein interactions define the output of metabolic pathways and regulate many cellular processes. Although diseases are often characterized by distortions in metabolic processes, efficient means to discover and study such interactions directly in cells have been lacking. A stringent implementation of proteome-wide cellular thermal shift assay (CETSA) to study interactions of human proteins with key nucleotide-based metabolites was developed and applied to 11 key cellular nucleotides, where previously experimentally confirmed protein-nucleotide interactions were well recaptured. Many predicted, but never experimentally confirmed, as well as novel protein-nucleotide interactions were discovered. Interactions included a range of different protein families where nucleotides serve as substrates, products, co-factors or regulators. In cells exposed to thymidine, a limiting precursor for DNA synthesis, both dose- and time-dependence of the intracellular binding events for sequentially generated thymidine metabolites were revealed. Interactions included known cancer targets in deoxyribonucleotide metabolism as well as novel interacting proteins. This stringent CETSA based strategy will be applicable for a wide range of metabolites and will therefore greatly facilitate the discovery and studies of interactions and specificities of the many thousand metabolites in human cells that remain uncharacterized.