Ultra-high performance concrete (UHPC) is a kind of high-tech composite material which shows superb characteristics compared to other kind of concrete such as self-compactness, compressive strength higher than 150 MPa and exceptional durability performances. In this research, compared to known commercially available UHPCs, a more eco-efficient paste for UHPC 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 (FA) as a waste material up to 25% of cement weight while with 13% and 16% of it the highest fluidity and strength could be achieved. In the next step finer fly ash was studied also. Ultra fine fly ash (UFFA) with mean particle size of 4.48  showed its applicability to be used in UHPC with 20% of cement weight substitution resulting in a paste with 153 MPa strength and 37.5 cm flow diameter. Furthermore, addition of at least 5% silica fume seems to be a prerequisite regarding strength gain of UHPC paste. Metakaoline as another pozzolanic material improved the strength of the paste while reduced the fluidity demonstrating its inability to be applied in UHPC with required high workability criteria.