Vehicular Ad-hoc Networks (VANETs) are an extension of Mobile Ad-hoc Networks (MANETs). However, many routing protocols of MANETs do not perform very well in VANETs due to their unique characteristics such as moving at high speed and road patterned movement. Thus, routing protocols and the other issues must be adapted to those VANETs characteristics. Moving at high speed causes links to be broken easily, which is not a good situation for real-time applications that need stable and reliable connection. Thus, in order to support those kinds of applications, we introduced probabilistic relay to improve the performance of routing protocols in VANETs. In this paper, we implemented probabilistic relay into OLSR and AODV protocols and compared their performance with the original ones using a computer simulation with realistic scenarios in VANETs. We evaluated those protocols under different metrics such as vehicle mobility and road segment length. We showed that probabilistic relay could provide a significant improvement in routing protocols' performance especially in packet delivery ratio.