Three different special quasirandom structures (SQS) of the substitutional hcp $A_{1-x}B_x$ binary random solutions ($x=0.25$, 0.5, and 0.75) are presented. These structures are able to mimic the most important pair and multi-site correlation functions corresponding to perfectly random hcp solutions at those compositions. Due to the relatively small size of the generated structures, they can be used to calculate the properties of random hcp alloys via first-principles methods. The structures are relaxed in order to find their lowest energy configurations at each composition. In some cases, it was found that full relaxation resulted in complete loss of their parental symmetry as hcp so geometry optimizations in which no local relaxations are allowed were also performed. In general, the first-principles results for the seven binary systems (Cd-Mg, Mg-Zr, Al-Mg, Mo-Ru, Hf-Ti, Hf-Zr, and Ti-Zr) show good agreement with both formation enthalpy and lattice parameters measurements from experiments. It is concluded that the SQSs presented in this work can be widely used to study the behavior of random hcp solutions.