Ultra-High Performance Concrete (UHPC) is an advanced cement-based construction material with extremely high compressive strength (over 150 MPa), high ductility, and exceptional durability properties. In general, UHPC is designed by optimizing the fine and ultrafine aggregates at the micro-scale level, a low water/binder ratio with added superplasticizer, and steel fibers. A high packing density among the ingredients is a key factor in UHPC design, as high packing density lowers the porosity of concrete thereby increasing the strength and durability properties. This experimental investigation aims to design a compacted cementitious matrix for UHPC, using the modified Andreasen and Andersen particle packing model. In addition, the Puntke test was also carried out to obtain the packing density of concrete mixtures. The cement is partially replaced by commonly available cement replacements such as silica fume to produce binary mixtures. The workability and compressive strength tests are performed on the designed UHPC. Finally, based on the results obtained, relevant conclusions regarding the effect of different cement replacements on workability and compressive strength of concrete have been drawn.