Tumor cells communicate with stromal cells, including cancer-associated fibroblasts (CAFs) and tumor-associated macrophages (TAMs), to form microenvironment inhibiting immune responses. Regulatory T cells (Tregs, CD4+CD25+FoxP3+) stimulate immune tolerance and facilitate tumor progression. We analyzed the changes in Treg frequencies assessed using flow cytometry in the peripheral blood of patients with urothelial bladder cancer before and after tumor-removal. Changes in Treg frequency were investigated in relation to clinicopathomorphological indicators of tumor malignancy and expression of RCAS1 on CAFs and TAMs. Higher Treg frequencies were observed in early phase of tumor growth (pTa-pT2), in larger tumors, with more aggressive type of invasion, and with expression of RCAS1. The later phase of tumor development, accompanied by a nonclassic differentiations and pT3-pT4 advancement, had lower number of tumor infiltrating lymphocytes (TILs) and lower Treg frequency. Furthermore, in pT2-pT4 tumors, a decreased post-surgery Treg frequency was associated with poorer prognosis: patients with the lowest frequency of Tregs died first. These findings strongly suggest that the Treg frequencies at later phase of tumor growth, associated with a low anti-tumor response, represent a new and important prognostic indicator in urinary bladder cancer.