In this letter, Z-complementary sequences are introduced. These sequences include the conventional complementary sequences as special cases. It is shown that, different from the normal complementary pair of binary sequences which exist only for very limited lengths, i.e., 2(a) 10(b) 26(c) for a, b, c >= 0, a Z-complementary pair of binary sequences exists for many more lengths. In addition, for a Z-complementary set with zero correlation zone Z, P binary sequences, each having length N, the maximum number of distinct Z-complementary mates is smaller than or equal to P [N/Z].