In this paper, a novel temporal-spatial variable scale algorithm (TSVSA) will be presented which proposes to solve the problem of detecting multiple moving objects from complex backgrounds. In general, moving objects have multi-scale characteristics in both spatial and temporal domains. In the spatial domain, objects differ in size while in temporal domain they differ in moving speed, which means each object has an optimum temporal-spatial detection window. Here we have formalized the detection of moving objects as the problem of searching in the temporal-spatial domain for multiple distinct optimum sub-spaces where significant evidence for motion exists. Such sub-spaces which differ in scale determine the positions in the temporal-spatial domain, moving traces and other such features of moving objects. Then a criterion for a measurement of motion salience is provided, and a fast recursive algorithm called “octree decomposition of the temporal-spatial domain” is proposed. The proposed method can detect and track the objects simultaneously, greatly reducing the incidence of false alarms and miss detection rate. Extensive experiments and detailed analysis are provided in this paper, and multiple experimental results have confirmed the validity and effectiveness of the proposed method.