User mobility in WLANs becomes more and more popular because of wide deployment of WLANs and numerous applications on it. Some of these applications, for example multimedia applications, require fast handoffs among access points to maintain the quality of service. In order to support multimedia applications for roaming users, IEEE 802.11i defines pre-authentication to reduce the re-authentication delay. The primary drawback of IEEE 802.11i pre-authentication is that the full 802.1x/EAP authentication consumes too much overhead. In this paper, the authors propose a new fast pre-authentication scheme that greatly improves the efficiency and achieves high security level.