Ultra-high performance concrete is a kind of high-tech composite material which shows superb characteristics such as self- compactness, compressive strength higher than 150 MPa, and exceptional durability performances compared to other kinds of concrete. In this research, compared to known commercially available UHPCs, a type of UHPC paste with greener pozzolans was developed. In this regard, cement and silica fume, as two main constituents of the prevalent UHPC compositions and particularly with high cost and environmental impacts, were replaced by fly ash as a waste material. It was found that the highest fluidity and strength could be achieved with 13% and 16% of fly ash substitution, respectively. Furthermore, ultra-fine fly ash with mean particle size of 4.48 μm showed its applicability to be used in UHPC with 20 wt.% cement substitution resulting in a paste with 153 MPa compressive strength and 37.5 cm flow diameter. Moreover, addition of at least 5% silica fume seems to be a prerequisite regarding strength gain of UHPC paste. Metakaolin as another pozzolanic material was studied. Although it improved the paste strength, it demonstrated lower fluidity and showed its inability to be applied in UHPC with required high workability.