In this paper, we define a new measure to compute spatio-temporal similarity between two trajectories of moving objects on road networks, which is known as spatio-temporal distance (STDist). In addition, we propose a new spatio-temporal similar trajectory search algorithm to retrieve similar trajectories based on the spatio-temporal distance, a combination of both spatial and temporal properties with respect to the motion of a given query trajectory. To support fast trajectories retrieval, we use a signature file method in which we generate signatures for segments of a trajectory. Our performance analysis shows that our algorithm outperforms the existing method in terms of searching similar trajectories of moving objects on road network.