The systems-wide analysis of biomolecules in time and space is key to our understanding of cellular function and heterogeneity in health and disease1. Remarkable technological progress in microscopy and multi-omics technologies enable increasingly data-rich descriptions of tissue heterogeneity2,3,4,5. Single cell sequencing, in particular, now routinely allows the mapping of cell types and states uncovering tremendous complexity6. Yet, an unaddressed challenge is the development of a method that would directly connect the visual dimension with the molecular phenotype and in particular with the unbiased characterization of proteomes, a close proxy for cellular function. Here we introduce Deep Visual Proteomics (DVP), which combines advances in artificial intelligence (AI)-driven image analysis of cellular phenotypes with automated single cell laser microdissection and ultra-high sensitivity mass spectrometry7. DVP links protein abundance to complex cellular or subcellular phenotypes while preserving spatial context. Individually excising nuclei from cell culture, we classified distinct cell states with proteomic profiles defined by known and novel proteins. AI also discovered rare cells with distinct morphology, whose potential function was revealed by proteomics. In a 17-year-old primary melanoma tissue, DVP revealed spatio-temporal cancer-specific protein changes in the native tissue environment, including an interplay between tumor related mRNA splicing in the metastatic vertical growth phase, the immune system, and the ECM remodeling. Thus, DVP provides unprecedented molecular insights into disease progression and metastisis while retaining spatial information.