In this paper, the requirement on optimal training sequences for single-carrier multi-antenna channel estimation with space-time block-coding is firstly derived based on time-domain analysis. It is then shown that the optimality requirement relates to a new concept called Z-periodic complementarity, and the desired optimal training sequences are in fact a class of Z-periodic complementary sequences which include the conventional periodic complementary sequences and L-perfect sequences as special cases. Definitions and constructions of the Z-periodic complementary binary sequences and their mates are given.