Despite decades of efforts, non-invasive sensitive detection of small malignant brain tumors still remains challenging. Here we report a dual-modality 124I-labeled gold nanostar (124I-GNS) probe for sensitive brain tumor imaging with positron emission tomography (PET) and subcellular tracking with two-photon photoluminescence (TPL) and electron microscopy (EM). Experiment results showed that the developed nanoprobe has potential to reach sub-millimeter intracranial brain tumor detection using PET scan, which is superior to any currently available non-invasive imaging modality. Microscopic examination using TPL and EM further confirmed that GNS nanoparticles permeated the brain tumor leaky vasculature and accumulated inside brain tumor cells following systemic administration. Selective brain tumor targeting by enhanced permeability and retention effect and ultrasensitive imaging render 124I-GNS nanoprobe promise for future brain tumor-related preclinical and translational applications.