In this paper, for balanced binary sequence pairs (BBSPs for short) of period N 1(mod 4), the optimality of their cross-correlation is determined. Next, a lower bound on the maximal out-of-phase autocorrelationmagnitude is established for BBSPs of period N 1(mod 4) with optimal cross-correlation. Furthermore, BBSPs with optimal cross-correlation whose maximal out-of-phase autocorrelation magnitude achieves the new lower bound are constructed based on the cyclotomy of order 4. These proposed sequences have a periodic total squared correlation value meeting the Ganapathy-Pados-Karystinos bound, and are therefore an option for use in asynchronous CDMA systems.