In recent years, many research works have focused on vertical handoff (VHO) decision algorithms. However, evaluation scenarios in different papers are often quite different and there is no consensus on how to evaluate performance of VHO algorithms. In this paper, we address this important issue by proposing an approach for systematic and thorough performance evaluation of VHO algorithms. Firstly we define the evaluation criteria for VHO with two metrics: matching ratio and average ping-pong number. Subsequently we analyze the general movement characteristics of mobile hosts and identify a set of novel performance evaluation models for VHO algorithms. Equipped with these models and evaluation criteria, we evaluate and analyze two types of decision algorithms: hysteresis based and dwelling-timer based algorithms. The results show a good match between simulation and analytical results.