Como parte de los acuerdos de la Conferencia de Yalta, se celebró un plebiscito en Mongolia en octubre de 1945 bajo los auspicios de las Naciones Unidas (ONU), con el voto abrumadoramente a favor de la independencia sobre la autonomía. La República de China reconoció a Mongolia en enero de 1946, y los dos países firmaron un tratado de amistad en febrero. En junio de 1946 Mongolia presentó la primera de varias solicitudes sin éxito para unirse a la ONU. Mientras tanto, Mongolia reconoció a la República Popular China en la proclamación de esta última en 1949 y estableció relaciones diplomáticas con Corea del Norte (1948), los países satélites soviéticos de Europa central y oriental (1950) y la India (1955). Mongolia obtuvo la admisión en la ONU en 1961, y en 1963 el Reino Unido se convirtió en el primer país occidental en establecer relaciones con Mongolia.
La década de 1950 fue una época de transición política y progreso económico. Choibalsan murió en 1952 en un hospital de Moscú, y Tsedenbal fue nombrado presidente (i. e., el equivalente de primer ministro) del Consejo de Ministros, (el órgano supremo del poder ejecutivo. En 1954, el secretario General del MPRP, Tsedenbal, fue derrocado por Dashiin Damba, que fue designado primer secretario del MPRP, pero en 1958, Tsedenbal retomó el control del partido, también como primer secretario, y destituyó a Damba por motivos ideológicos. La colectivización del pastoreo de ganado se completó en la década de 1950, ya que los pastores se vieron obligados a entregar todos sus animales, excepto algunos, a las grandes granjas cooperativas (negdel). El Ferrocarril Transcongoliano, construido conjuntamente por los mongoles y los soviéticos y completado en 1955, abarcó Mongolia de norte a sur y sirvió como símbolo de la solidaridad soviético-china, pero se construyó utilizando el ancho de vía soviético en lugar del ancho estándar utilizado en China. En 1958 Mongolia comenzó a asistir a las reuniones del Caem y se unió a esa organización en 1962.
Mongolia y China firmaron un tratado de amistad y asistencia mutua en 1960, y los dos países redemarcaron amistosamente la larga frontera entre ellos. Sin embargo, la disputa ideológica que se desarrolló entre la Unión Soviética y China sobre la unidad y el liderazgo del movimiento comunista agrió las relaciones de Mongolia con China. China criticó duramente a los soviéticos por su manejo de la crisis de misiles cubanos de octubre de 1962 con los Estados Unidos y dos años más tarde llevó a cabo su primera prueba de bomba atómica: los vientos predominantes transportaron lluvia radiactiva hacia el norte hacia territorio mongol. En enero de 1966, Mongolia y la Unión Soviética firmaron un nuevo tratado de amistad, cooperación y asistencia mutua que incluía protocolos secretos que permitían a los soviéticos estacionar tropas, aviones y misiles en Mongolia. Las relaciones sino-soviéticas degeneraron aún más después de los enfrentamientos entre sus tropas a lo largo de su frontera en el río Ussuri (Wusuli) en marzo de 1969. Mientras tanto, el líder chino Mao Zedong había lanzado el movimiento que se conoció como la Revolución Cultural (1966-76), durante la cual los mongoles de Mongolia Interior en particular sufrieron considerablemente.
En 1949, el MPRP había condenado cómo se enseñaba la historia de Mongolia, afirmando que aquellos con puntos de vista «nacionalistas burgueses» estaban ensalzando las conquistas de Genghis Khan y el pasado «feudal» de Mongolia a expensas de los logros del partido y la revolución mongola. Sin embargo, a medida que se acercaba el 800 aniversario del nacimiento de Genghis Khan en 1962, el partido decidió organizar celebraciones en su honor que incluirían la inauguración de un nuevo monumento en su honor, la entrega de discursos y la emisión de un juego de sellos postales conmemorativos. Sin embargo, tras las críticas soviéticas que etiquetaban a Genghis de «reaccionario» cuyo «yugo tártaro-mongol» había devastado a Rusia, Mongolia canceló rápidamente las celebraciones y retiró los sellos. Siguió una nueva evaluación del MPRP de Genghis Khan, que también lo consideraba un reaccionario y que le acreditaba solo por unificar a las tribus mongolas. Cualquier desviación de esa línea se considera promoción no deseada del nacionalismo y no se tolera. Esta política sofocó prácticamente toda la discusión sobre Genghis Khan y el nacionalismo mongol durante los siguientes 40 años.
Las tensiones entre Mongolia y China se intensificaron a lo largo de la década de 1970. Mongolia acusó a China de querer anexionarse Mongolia y, como pretexto para sus reclamos territoriales sobre el territorio mongol, de promover a Genghis Khan como emperador de la dinastía Yuan. China, durante sus propias celebraciones del 800 aniversario, respondió criticando a la Unión Soviética por» ocupar » Mongolia estacionando tropas y equipo militar allí. En abril de 1978, China pidió la retirada soviética de Mongolia, y el primer ministro Tsedenbal visitó rápidamente una unidad del ejército soviético estacionada en Mongolia para agradecerle por proteger al país contra la «amenaza china». Mongolia comenzó a expulsar a los inmigrantes chinos a principios de 1979, acusándolos de «complots expansionistas», que exacerbaron aún más la desconfianza entre los dos países. Las tensiones en la región disminuyeron considerablemente a mediados de la década de 1980, cuando los líderes soviéticos y mongoles tomaron medidas para normalizar las relaciones con China. En 1986 se restablecieron las relaciones diplomáticas entre Mongolia y China.