We report the results of the first search for the decay $B_s^0 rightarrow eta^prime eta$ using $121.4~textrm{fb}^{-1}$ of data collected at the $Upsilon(5S)$ resonance with the Belle detector at the KEKB asymmetric-energy $e^+e^-$ collider. We observe no significant signal and set a 90% confidence-level upper limit of %$7.1 times 10^{-5}$ $6.5 times 10^{-5}$ on the branching fraction of this decay.