Pseudo-random sequences with good statistical property, such as low autocorrelation, high linear complexity and 2-adic complexity, have been widely applied to designing reliable stream ciphers. In this paper, we explicitly determine the 2-adic complexities of two classes of generalized cyclotomic binary sequences with order 4. Our results show that the 2-adic complexities of both of the sequences attain the maximum. Thus, they are large enough to resist the attack of the rational approximation algorithm for feedback with carry shift registers. We also present some examples to illustrate the validity of the results by Magma programs.