Việt Nam và Mông Cổ là hai nước có quan hệ hữu nghị truyền thống lâu đời. Hai nước thiết lập quan hệ ngoại giao ngày 17/11/1954, đánh dấu mốc quan trọng trong lịch sử quan hệ hai nước. Mông Cổ là một trong những nước sớm thiết lập quan hệ ngoại giao với Việt Nam và Việt Nam là nước đầu tiên trong khu vực Đông Nam Á mà Mông Cổ thiết lập quan hệ ngoại giao.
Tháng 7/1955, Chủ tịch Hồ Chí Minh đã dẫn đầu Đoàn đại biểu Đảng và Chính phủ Việt Nam sang thăm chính thức Mông Cổ, mở đầu cho việc phát triển quan hệ hữu nghị giữa hai nước.
Ngày 9/6/1959, Mông Cổ mở Cơ quan đại diện thường trú tại Hà Nội.
Ngày 13/2/1960, Việt Nam mở Cơ quan đại diện thường trú tại Ulaanbaatar; Hội Hữu nghị Mông Cổ-Việt Nam được thành lập.
Năm 1961, hai nước ký Hiệp ước hữu nghị và hợp tác đầu tiên (hai lần sau vào các năm 1979, 2000); Hội hữu nghị Việt Nam-Mông Cổ được thành lập.
Ngày 3/12/1979, hai nước thành lập Ủy ban liên Chính phủ về hợp tác kinh tế-thương mại, khoa học và kỹ thuật.
Năm 2000, hai nước thiết lập cơ chế Tham khảo chính trị cấp Thứ trưởng Ngoại giao.
Kể từ khi thiết lập quan hệ ngoại giao đến nay, Việt Nam và Mông Cổ luôn phối hợp chặt chẽ trên nhiều lĩnh vực, dành cho nhau sự giúp đỡ vô tư, trong sáng. Mối quan hệ ấy ngày càng được củng cố, phát triển thông qua các chuyến thăm và làm việc thường xuyên của lãnh đạo cấp cao hai nước. Những chuyến thăm này đã góp phần quan trọng trong việc tăng cường quan hệ chính trị giữa Việt Nam và Mông Cổ.
Mông Cổ rất coi trọng quan hệ với Việt Nam, coi Việt Nam là một trong những đối tác quan trọng nhất tại khu vực Đông Nam Á. Việt Nam cũng luôn coi trọng mối quan hệ hữu nghị, đánh giá cao tiềm năng hợp tác phát triển với Mông Cổ và mong muốn làm sâu sắc hơn nữa quan hệ hữu nghị truyền thống với Mông Cổ.