Ngày 14-10-1964 Khrusev bị loại ra khỏi bộ chính trị, và được thay thế. Nhận thấy đây là một cơ hội để TQ được Liên Xô tiếp tục giúp đỡ cho hoàn thành kế hoạch chế tạo hoả tiễn, mà vốn đã bị đình trệ từ khi Liên Xô rút cố vấn kỹ thuật về từ năm 1959, Mao bắn tiếng qua đại sứ Liên Xô là ông mong muốn cải thiện quan hệ hai nước. Brezhnev cũng muốn vậy, thế nhưng khi biết là Mao chỉ muốn thủ lợi cho riêng mình, Brezhnev bèn thử dò tìm một cơ hội lật đổ Mao. Tại bữa tiệc chiêu đãi phái đoàn Chu Ân Lai tại điện Kreml (Kremlin) ngày 7-11, bộ trưởng quốc phòng Liên Xô, Malinovsky, nói với Chu: "Chúng tôi không muốn cả Mao lẫn Khrusev đứng giữa quan hệ của hai chúng ta". Làm như không biết ông này nói gì, Chu bỏ đi chỗ khác. Malinovsky quay sang thống chế Hạ Long, khi đó là quyền Tổng tư lệnh quân đội TQ: "Chúng tôi đã gạt bỏ Khrusev, các ông hãy gạt bỏ Mao đi rồi ta sẽ có quan hệ tốt hơn". Hạ Long phản kháng vài câu rồi cũng bỏ đi. Tối hôm đó, Chu điện cho Mao hay mọi chuyện. Ngày hôm sau, Chu chính thức phản đối với Brezhnev khi ông này và bốn cán bộ cao cấp (không có Malinovsky) tới thăm ông ở tư dinh, Breznev đổ thừa là Malinovsky say, nói bậy, thế nhưng sự kiện là Malinovsky không bị khiển trách gì chứng tỏ ông này chỉ làm theo ý của Brezhnev.

Ý thức rằng Brezhnev đang âm mưu lật đổ ông, Mao không cho một cán bộ cấp cao nào của TQ được sang thăm Liên Xô nữa. Lệnh này được tuân thủ cho tới khi Mao chết. Chỉ một người duy nhất được ngừng chân ở Moscow trên đường đi dự đại hội đảng Romania vào năm 1965 là Đặng Tiểu Bình, chứng minh là ông này được Mao hoàn toàn tín nhiệm. Khi Hồ Chí Minh chết (1969), e ngại sẽ gặp mặt phái đoàn Liên Xô, Chu Ân Lai đã bay sang Hà nội và sau đó bay về TQ trước khi đám tang bắt đầu. Đám tang của Hồ chỉ có sự có mặt của một phái đoàn cấp thấp của TQ. Mao cũng đánh giá là Bắc Kinh chỉ cách Ngoại Mông của Liên Xô chỉ 500 cây số, đa số là đồng ruộng trống trải và bằng phẳng, nên rất dễ trở thành mục tiêu tấn công của xe tăng Liên Xô. Để đề phòng chuyện này, Mao cho xây dựng một số đồi núi nhân tạo giống như những pháo đài khổng lồ ở bắc TQ. Kế hoạch này bị huỷ bỏ vài năm sau vì quá tốn kém.

Một số cán bộ cao cấp có liên hệ với Liên Xô cũng bị thanh trừng. Thống chế Hạ Long bị bắt và bị đưa đi cải tạo cho tới chết (1969). Thứ trưởng quốc phòng TQ, Xu Guangda, chỉ vì có mặt ở Liên Xô trong lúc Malinovsky nói câu đó đã bị thẩm vấn tới 416 lần trong 18 tháng.

Cũng trong năm 1965 một cuộc họp thượng đỉnh các nước châu Á và Phi châu dự trù sẽ được tổ chức ở Algeria. Để hy vọng kiếm phiếu, Mao ve vãn tổng thống Sukarno của Indonesia bằng quà cáp và hứa hẹn sẽ giúp Indonesia chế bom nguyên tử. Mao cũng hứa hẹn y như vậy với Ai cập. Mao cũng hứa sẽ xây dựng cho Zambia một hệ thống đường ray xe lửa dài tới 2000 cây số, một kế hoạch lên tới 1 tỷ Mỹ kim. Xui cho Mao là tổng thống Ben Bella của nước chủ nhà Algeria bị lật đổ trong một cuộc chính biến xảy ra chỉ 10 ngày trước ngày hội nghị khai mạc. Vì thế cuộc hội nghị thượng đỉnh bị huỷ bỏ, dù Mao hết sức vận động cửa hậu. Ước mộng của Mao được làm chủ một hội nghị quốc tế Á-Phi lại bị tan tành.

Mao cũng bị thất vọng khi không sai khiến được Pakistan đánh Ấn độ. Tháng 9-1965, Ấn độ và Pakistan xảy ra chiến tranh biên giới. Mao cũng dàn quân ở biên giới TQ-Ấn, và ra tối hậu thư cho Ấn độ trong ba ngày phải giải giới một số căn cứ của Ấn đặt dọc theo biên giới hai nước, ở những chỗ mà Mao cho là thuộc đất TQ. Ấn độ đề nghị cùng thanh tra, nhưng Mao khước từ. Ý đồ của Mao là Ấn độ không thể nào đương đầu với hai mặt trận một lúc: Pakistan và TQ. Ý đồ này bị thất bại vì Pakistan bỗng nhiên chấp nhận đình chiến, theo đề nghị của Liên hiệp quốc. Pakistan cho Mao hay là một cuộc chiến tranh với Ấn độ sẽ rất tốn kém. Cuộc chiến tranh biên giới giữa Ấn và TQ vì thế cũng tạm chấm dứt.

Mao cũng là kẻ đỡ đầu cho lực lượng cộng sản ở Thái. Ngày 7-8-1965 đảng cộng sản Thái đụng độ với lực lượng quân đội của chính phủ theo lời khuyến dụ của Mao, nhưng không đem lại kết quả như ý.

Thất vọng lớn nhất của Mao về mặt đối ngoại trong năm 1965 phải nói là cuộc đảo chánh ở Indonesia.

Tổng thống Sukarno thân Bắc Kinh, nên đã giao cho đảng cộng sản Indonesia nắm giữ một số cơ quan quan trọng trong chính quyền và quân đội. Đây là một đảng cộng sản lớn nhất không nắm chính quyền vì có tới 35 triệu đảng viên. Ngày 30-9 đảng cộng sản tổ chức một cuộc đảo chính để giành chính quyền theo lời khuyên của Mao: "Phải nắm lấy cơ hội mà giành chính quyền", tổng tư lệnh quân đội và năm viên tướng khác bị bắt giữ và bị giết. Thế nhưng âm mưu này đã bị tiết lộ, và một viên tướng không nằm trong danh sách phải cần bị bắt của phe đảo chánh đã lật ngược được tình thế. Tướng Suharto ban lệnh bắt và tàn sát cả trăm ngàn người, đảng viên đảng cộng sản, cảm tình viên cũng như thường dân. Tất cả thành viên của bộ chính trị đều bị giết, ngoại trừ một người, Jusuf Adjitorop, khi đó đang ở TQ.

Về mặt đối nội, lợi dụng uy tín Mao xuống thấp, Lưu Thiếu Kỳ đã tạo cho mình được một vị trí ngang ngửa với Mao. Báo chí TQ không còn chỉ tôn vinh Mao Chủ tịch, mà luôn luôn Mao Chủ tịch và Lưu Chủ tịch (Lưu là Chủ tịch nước, Mao là Chủ tịch đảng). Vì là người đã đưa TQ ra khỏi nạn chết đói, Lưu được rất nhiều người ủng hộ, kể cả từ những kẻ đã từng ủng hộ Mao trước kia. Thậm chí, có người đề nghị chỉ treo tranh Lưu (không treo tranh Mao) trên tường Thiên An môn, nhưng Lưu đã bác bỏ ý kiến đó ngay lập tức.