Background Fine needle aspiration cytology (FNAC) is usually used to evaluate palpable nodes in patients with melanoma. The goal of our study is to review the sensitivity and specificity of this technique when applied to palpable but also to nonpalpable nodes. Methods FNAC was performed during 1984-2007 in 1279 patients with suspicious lesions and/or lymph nodes. Indications for biopsy included increased size and/or palpability of nodes or abnormal ultrasound findings such as increased perfusion or focal lesions within the lymph nodes. The sensitivity, specificity, and positive and negative predictive values of FNACs guided by palpation or ultrasound were calculated for all patients and for subgroups of patients with palpable nodes or nonpalpable but sonomorphologically suspicious nodes. Results A total of 2446 FNACs were performed in 1279 melanoma patients, of which 2011 (82.2%) FNACs had clinically or histologically confirmed results. Increased size and/or palpability of nodes was observed in 376 (29.4%) of 1279 patients, and abnormal ultrasound findings occurred for 903 (70.6%), indicating that a biopsy was needed. FNACs guided by palpation had sensitivity, specificity, and positive and negative predictive values similar to that of FNACs guided by ultrasound (sensitivity = 98.4% vs 97.2%, specificity = 100% vs 99.8%, positive predictive value = 100% vs 99.9%, and negative predictive value = 95.2% vs 96.4%, for palpation-guided FNACs vs ultrasound-guided FNACs, respectively). Results did not differ between patients with the palpable nodes and patients with nonpalpable but sonomorphologically suspicious nodes. Conclusions Ultrasound-guided FNAC of suspicious lymph nodes and lesions in melanoma patients has a high sensitivity and specificity, and FNAC should not be limited to palpable nodes. FNAC of normal-sized nodes and/or lymph nodes with abnormal ultrasound findings can be used to identify early metastatic disease.