Besides tumor cells, the tumor microenvironment harbors a variety of host-derived cells, such as endothelial cells, fibroblasts, innate and adaptive immune cells. It is a complex and highly dynamic environment, providing very important cues to tumor development and progression. Tumor-associated endothelial cells play a key role in this process. On the one hand, they form tumor-associated (angiogenic) vessels through sprouting from locally preexisting vessels or recruitment of bone marrow-derived endothelial progenitor cells, to provide nutritional support to the growing tumor. On the other hand, they are the interface between circulating blood cells, tumor cells and the extracellular matrix, thereby playing a central role in controlling leukocyte recruitment, tumor cell behavior and metastasis formation. Hypoxia is a critical parameter modulating the tumor microenvironment and endothelial/tumor cell interactions. Under hypoxic stress, tumor cells produce factors that promote tumor angiogenesis, tumor cell motility and metastasis. Among these factors, VEGF, a main angiogenesis modulator, can also play a critical role in the control of immune tolerance. This review discusses some aspects of the role of endothelial cells within tumor microenvironment and emphasizes their interaction with tumor cells, the extracellular matrix and with immune killer cells. We will also address the role played by circulating endothelial progenitor cells and illustrate their features and mechanism of recruitment to the tumor microenvironment and their role in tumor angiogenesis.