In this letter, we present a new method of alleviating the deterioration in the quality of real-time video service during vertical handover (VHO). The proposed method stochastically delays the starting time of the service disruption of VHO in order to reduce the number of lost frames caused by the inter-frame dependency of multi-layered video traffic. The results show that the proposed method significantly decreases the average frame loss time at the sacrifice of an increased handover execution time by one half of the group of picture (GOP) interval of the video traffic.