The development of new blood and/or lymphatic vessels is a pre-requisite for Melanoma growth and spread through metastasis. With the view to better identify and characterize the source of de novo endothelium in cancer, we utilised flow cytometry and immunofluorescence to characterise endothelial populations in B16 melanoma. We identify endothelial cells derived from resident vascular beds and not from hematopoietic lineages. Among Lin-CD34+ cells, expression levels of VEGFR2 and CD31 defined three distinct endothelial sub-populations. Furthermore, using lineage tracing of VE_cadherin expressing endothelial cells (Cdh5-Cre/ER RosaYFP), we demonstrate a maturation sequence from progenitor (P) via transit amplifying (TA) to fully differentiated (D) cells in B16 melanoma as well as in skin wounds. Sox18, a transcription factor essential in vascular development was then considered as a functional marker of the progenitor population. Sox18 expression is lost in the adult, with reexpression reported in endothelial cells only in pathogenic situations of angiogenesis. We utilized Sox18CreER/Rosa-YFP reporter mice and showed that progenitors activate Sox18. Fate tracking over multiple tumour time-points revealed that by day 5 after melanoma cell injection, only progenitors have been recruited to the tumour; by day 10, there is a sequential progression to fully differentiated cells. Immunohistochemistry for vascular markers on these tumours demonstrate that progenitor cells originate from venous vascular beds and can give rise to de novo arterial, veinous and lymphatic structures in the tumour. This highlights the usefulness of strategies targeting vascular progenitors in cancer.