Disclosed herein are a method and system for appearance-invariant tracking of an object in an image sequence. A track is associated with the image sequence, wherein the track has an associated track signature comprising at least one mode. The method detects the object in a frame of the image sequence (1020). A representative signature is associated with the detected object. The method determines a spatial difference measure between the track and the detected object, and determines, for each mode of the track signature, a visual difference (1410) between the mode of the track signature and the representative signature to obtain a lowest determined visual difference (1420). The method then utilises the spatial difference measure and the lowest determined visual difference to perform at least one of the following steps of: (i) associating the detected object with the track (1440), and (ii) adding a new mode to the track signature (1460), based on the representative signature.