In this study, we solve an online multi-object problem which finds object states (i.e. locations and sizes) while conserving their identifications in online-provided images and detections. We handle this problem based on a tracking-by-detection approach by linking (or associating) detections between frames. For more accurate online association, we propose novel online appearance learning with discrete fourier transform and partial least square analysis (PLS). We first transform each object image into a Fourier image in order to extract meaningful features on a frequency domain. We then learn PLS subspaces which can discriminate frequency features of different objects. In addition, we incorporate the proposed appearance learning into the recent confidence-based association method, and extensively compare our methods with the state-of-the-art methods on MOT benchmark challenge datasets.