Kaposi's sarcoma (KS) is the most prevalent AIDS-associated tumor. We report a 44-year-old Japanese man with advanced AIDS-associated KS, which was spread over bilateral pulmonary parenchyma. He was initially treated with combination chemotherapy with a partial response. Upon the recurrence of his KS two months after the completion of the combination chemotherapy, the patient received paclitaxel, which brought about a complete response. Highly active antiretrovial therapy (HAART) was initiated three months before the combination chemotherapy, and the CD4+ T-cell count had risen before starting paclitaxel. His dinical course suggests that paclitaxel was highly effective for KS disease control as previously reported, and that immune restoration with HAART is crucial in the treatment of KS.