Extramedullary leukemia (EML) is an uncommon clinical diagnosis in patients with acute nonlymphocytic leukemia (ANLL). Prostatic EML as a first site of ANLL relapse is even more rare. To our knowledge, only three cases have been reported. We describe an additional case of prostatic EML as a site of ANLL relapse. An asymptomatic male in ANLL remission was found to have a normal prostate-specific antigen (PSA) and a myeloid leukemic infiltrate in a newly diagnosed prostate nodule. Staging was negative for ANLL relapse. Local prostate radiation resolved the nodule, and the post-treatment needle biopsies were negative. He subsequently developed clinical relapse in bone marrow, blood, and small bowel and received salvage chemotherapy with mitoxantrone and etoposide.