Tensor low-rank representation (TLRR) has attracted increasing attention in recent years due to its effectiveness in capturing the intrinsic low-rank structure of tensor data. However, it is known that TLRR suffers from high computational complexity for large-scale data because it minimizes the tensor rank of the representation tensor whose size is proportional to the sample size. This paper develops a streaming algorithm—termed online low-rank tensor subspace clustering (OLRTSC)—for low-rank tensor data recovery and clustering based on the tensor singular value decomposition (t-SVD) algebraic framework. The key idea of OLRTSC is the non-convex reformulation of the objective function of TLRR by decomposing the tensor nuclear norm into an explicit tensor product of two low-rank tensors, which can be solved by leveraging the stochastic optimization technique. Compared to batch TLRR, OLRTSC is online by nature, can handle dynamic data, avoids computing t-SVD of the representation tensor, and reduces the storage cost significantly. This paper provides the theoretical guarantee that the sequence of the solutions produced by OLRTSC converges almost surely to a stationary point of the objective function. Moreover, an extension of OLRTSC is also proposed to handle the case when parts of the data are missing. Finally, experimental results on both synthetic and real data demonstrate the efficiency and robustness of the proposed approaches.