Fire detection is one of the most interesting issues for surveillance. The existing approaches for the fire detection suffer from a high false positive ratio. To solve the problems, we present a patch-based fire detection algorithm with online outlier learning. In the proposed algorithm, the candidates of fire are obtained in the form of patch, while the classical candidates have been based on pixels or blobs. Because the patches of fire have more distinctive shape than the entire fire, the shape classifier can recognize the candidates correctly from fire-like outliers. In addition, we propose an online outlier learning scheme which handles the irregularity of fire based on the repeatability of shape in time. The proposed algorithm is experimented with new challenging dataset, consisting of 50 positive videos with fire and 44 negative ones with fire-like outliers. By evaluating on the dataset, we validate the performance of our algorithm qualitatively and quantitatively.