Prostatic stromal sarcomas (PSS) are rare solid organ mesenchymal sarcomas. PSS may pose difficult diagnostic challenges on fine needle aspiration biopsy. We report a 48-year-old man diagnosed with metastatic high grade prostatic stromal sarcoma by a CT-scan guided fine needle aspiration (FNA) biopsy of a right lower lung lobe nodule. We reviewed the literature on the epidemiologic, cyto-histological, and immunophenotypic findings and discussed the differential diagnosis for this rare entity.