Fog computing provides computation and services to the edge of networks to support real-time applications. The latency performance is a crucial metric in fog computing. In this article, we consider a computation offloading problem in a fog network with unknown dynamics. In this network, mobile users can offload their computational tasks to neighborhood fog nodes (FNs) in each time slot. The queue of arrival tasks at each FN follows a Markov model with unknown statistics. In order to provide a satisfactory quality of experience, the network latency needs to be minimized. In this article, we construct an offloading policy with interleaved exploration and exploitation epochs to solve the sequential FN selection problem. An upper bound of regret is derived to show the effectiveness of the proposed method. The proposed policy is optimal in the sense that it achieves a regret with sublinear order. In addition, the proposed policy can be applied to both single-user setting and multiuser setting. Simulation results show that when compared with the existing offloading algorithms, the proposed algorithm can reduce the average latency by 7%-47% in the single-user setting, and 91% in the multiuser setting. © 2014 IEEE.