Công tác đối ngoại quân sự, quốc phòng luôn được Quân ủy Trung ương quan tâm lãnh đạo và phân công một đồng chí Thứ trưởng chỉ đạo trực tiếp. Từ sau Đại hội toàn quân lần thứ 7 (năm 2000), Trung tướng Nguyễn Huy Hiệu (năm 2003 được phong quân hàm Thượng tướng), Ủy viên Trung ương Đảng, Ủy viên Thường vụ Đảng ủy Quân sự Trung ương (sau đổi lại tên cũ là Quân ủy Trung ương) được phân công trực tiếp phụ trách công tác đối ngoại quân sự và một số nhiệm vụ khác có liên quan tới nhiệm vụ đối ngoại. Đây là thuận lợi mới đối với Cục Đối ngoại, Bộ Quốc phòng nói riêng và công tác đối ngoại quân sự, quốc phòng nói chung, vì lần đầu tiên, một đồng chí Ủy viên Thường vụ trực tiếp theo dõi và chỉ đạo công việc chuyên môn của đơn vị.
Trung tướng Nguyễn Huy Hiệu là vị tướng trưởng thành qua trận mạc, Anh hùng lực lượng vũ trang nhân dân, vốn là Tư lệnh Quân đoàn 1, Phó Tổng Tham mưu trưởng Quân đội nhân dân Việt Nam, nhưng Ông cũng đã có không ít dịp tiếp xúc, giao lưu quốc tế khi là thành viên đoàn Ủy ban Hòa bình Thế giới của Việt Nam đi thăm và cám ơn các nước xã hội chủ nghĩa anh em những năm 1980.
Nhận công tác phụ trách mảng công tác này trong tình hình thế giới, khu vực tiếp tục diễn biến phức tạp và khó lường hơn trước, Ông đến gặp, làm việc ngay với cán bộ Cục, mở rộng đến các chỉ huy Phòng, Ban Cục Đối ngoại. Trong buổi đầu ấy, ông điểm lại tình hình thế giới và trong nước có liên quan tới đối ngoại quân sự (từ năm 2011 gọi là đối ngoại quốc phòng) và yêu cầu cán bộ, chiến sĩ, quân nhân chuyên nghiệp, công nhân viên quốc phòng công tác trong lực lượng đối ngoại quân sự nhận thức sâu sắc hơn nữa về mục tiêu, nhiệm vụ bảo vệ Tổ quốc. Ông phổ biến chủ trương của Thường vụ Đảng ủy Quân sự Trung ương: chủ động, linh hoạt và coi trọng tính thiết thực trong thúc đẩy hợp tác đối với các mối quan hệ hữu nghị hiện có, ưu tiên quan hệ với các nước láng giềng; từng bước mở rộng quan hệ với một số nước công nghiệp phát triển và ở một vài nước khác; tích cực phối hợp góp phần giải quyết cơ bản những vấn đề tồn tại về biên giới, lãnh thổ, tạo ra vành đai biên giới hòa bình, ổn định lâu dài với các nước; tham gia các hoạt động đa phương và thực hiện tốt các thoả thuận quốc tế đã ký kết.
Trong những lần chủ trì giao bao công tác đối ngoại toàn quân, ông thường nhắc: thế giới ngày nay phụ thuộc lẫn nhau sâu sắc hơn trướ; quốc phòng, an ninh của Việt Nam không thể tách rời an ninh khu vực, an ninh của thế giới; hợp tác quân sự, quốc phòng là một trong những yếu tố quan trọng để duy trì hoà bình, ổn định, đồng thời cũng là một yếu tố quan trọng để thực hiện các mục tiêu quốc phòng của chúng ta. Vì vậy, chúng ta chủ trương mở rộng đối ngoại quân sự, nâng cao hiệu quả các mối quan hệ song phương, tích cực tham gia hợp tác quốc phòng đa phương, với các hình thức từ thấp đến cao, như trao đổi các đoàn quân sự các cấp, tham vấn – đối thoại quốc phòng, trước tiên đi từ cấp Cục Đối ngoại, sau này chín muồi sẽ mở rộng đối thoại đến cấp Bộ, nhằm tăng cường hiểu biết lẫn nhau, ngăn ngừa xung đột, chiến tranh.
Đối với Mỹ, tiếp tục hợp tác tìm kiếm lính Mỹ mất tích trong chiến tranh ở Việt Nam (MIA) từ những năm trước, ông chỉ đạo Cục Đối ngoại tiếp xúc với phía Mỹ để giải quyết chất đi-ô-xin (chất độc màu da cam), nổi cộm là ở các sân bay quân sự Biên Hòa, Đà Nẵng, Phù Cát, chất CS trên đèo Cù Mông.
Cục Đối ngoại điện đề nghị Đại tá Nguyễn Ngọc Giao, Tùy viên Quốc phòng ta tại Washington làm việc với đại diện Bộ Quốc phòng Mỹ về nội dung này và mấy ngày sau, Đại tá Nguyễn Ngọc Giao điện về: đã tiếp xúc với ông Luis Stern (Lu-i Xtơn), phụ trách hướng Đông Nam Á, Văn phòng Bộ Quốc phòng Mỹ và được ông này trả lời: vấn đề chất độc da cam đã gác lại khi hai nước bình thường hóa quan hệ năm 1995 (!). Trước khi Bộ trưởng Quốc phòng, Đại tướng Phạm Văn Trà thăm chính thức Mỹ tháng 11-2003, Tướng Hiệu chỉ đạo trực tiếp cho Phó Cục trưởng Đối ngoại phụ trách hướng châu Mỹ: phải đấu tranh để Mỹ ít nhất phải thừa nhận trách nhiệm nhân đạo đối với các nạn nhân chất độc màu da cam ở Việt Nam, cao nhất là thừa nhận trách nhiệm pháp lý.
Khi gặp Phó Cục trưởng Đối ngoại ta, Đại tá, Tùy viên Quốc phòng Mỹ tại Việt Nam Stephan Ball chăm chú lắng nghe, ghi chép ý kiến của phía Việt Nam, nhưng trả lời rằng chiến tranh kết thúc đã gần 30 năm, việc này không thuộc thẩm quyền Bộ Quốc phòng, mà phải xin ý kiến Quốc hội Mỹ. Ta kiên trì nhắc lại rằng: chúng ta “gác lại quá khứ”, chứ không quên quá khứ; nay phía Mỹ cần củng Việt Nam khắc phục hậu quả việc này, ít nhất là dựa trên đạo lý. Đại tá, Tùy viên Quốc phòng Mỹ cho rằng việc này hết sức khó, nhưng sẽ báo cáo đầy đủ về Washington. Quả nhiên, sau khi Đại tướng Phạm Văn Trà kết thúc chuyến thăm Mỹ, Bộ Quốc phòng cùng Ủy ban 33 tổ chức một cuộc hội thảo chuyên đề tại Nhà khách Bộ Quốc phòng 33a Phạm Ngũ Lão và mời đại diện Đại sứ quán Mỹ tới dự. Đáng chú ý, Đại sứ đặc mệnh toàn quyền Hợp chúng quốc Hoa Kỳ Mai-cơn Ma-rin (Michael W. Marine) đã xuất hiện tại hội thảo này. Sự có mặt của người đại diện Tổng thống Mỹ và nước Mỹ tại hội thảo này chứng tỏ ta đã kéo được người Mỹ có thẩm quyền vào cuộc để giải quyết khía cạnh nhân đạo. Đây chính là thắng lợi của đối ngoại quân sự, trong đó có công lao chỉ đạo của Thượng tướng Hiệu. Từ hoạt động này, diễn ra bước khởi đầu tẩy độc thành công tại sân bay Đà Nẵng và công việc đó nay vẫn tiếp tục tại sân bay Biên Hòa.
Không chỉ tập trung giải quyết hậu quả chiến tranh như rà phá bom mìn, lập bản đồ khu vực bị ném bom, tìm kiếm người Mỹ mất tích trong chiến tranh, Thượng tướng Hiệu còn gợi ý phía Mỹ, nhất là các cựu chiến binh Mỹ đã từng tham chiến ở Việt Nam, giúp cung cấp thông tin về bộ đội Việt Nam hy sinh nhưng chưa tìm được hài cốt.
Nếu như hợp tác quốc phòng giữa Việt Nam và Mỹ được xác lập ngay từ khi bình thường hóa năm 1995, thì giai đoạn từ 2000 đến 2011 đã có những thay đổi ấn tượng, bằng việc diễn ra các chuyến thăm chính thức Việt Nam lần đầu tiên của Bộ trưởng Quốc phòng Mỹ Uy-li-am Cô-hen (William Cohen) tháng 3-2000 và Bộ trưởng Quốc phòng Việt Nam, Đại tướng Phạm Văn Trà thăm Mỹ tháng 11/2003, thực sự đưa quan hệ hai nước lên tầm cao mới. Từ năm 2003, Việt Nam và Mỹ tiến hành Đối thoại Quốc phòng song phương (BDD- Bilateral Defence Dialogue) do Cục Đối ngoại hai bên đồng chủ trì, lần lượt diễn ra ở Hà Nội và Washington, Hawaii.
Sau chuyến thăm Mỹ của Đại tướng Phạm Văn Trà, năm 2004, Thượng tướng Nguyễn Huy Hiệu chủ trì làm việc với Cục Đối ngoại, Cục Cán bộ, các Quân chủng Không quân, Hải quân, Bộ đội Biên phòng về nhu cầu đào tạo cán bộ. Ông nhấn mạnh: trước đây Quân đội ta chủ yếu được đào tạo kiến thức kỹ thuật quân sự ở Liên Xô, Trung Quốc, một số nước xã hội chủ nghĩa khác. Trong bối cảnh mới, ta có điều kiện mở mang kiến thức sang các nước châu Âu và nay là Mỹ; đây là thời cơ ta không nên bỏ lỡ. Phải chọn lựa cán bộ đi học là những đồng chí có phẩm chất tốt, trung thành, đã qua thực tế công tác, có ngoại ngữ tiếng Anh, đảm bảo 100% đi học xong phải về đủ. Sau đó, ông đề nghị cử đoàn do Phó Cục trưởng Đối ngoại dẫn đầu cùng Cục trưởng Cục Cán bộ và cán bộ các cơ quan Bộ đi khảo sát một số cơ sở đào tạo của quân đội Mỹ tại Hawait, Washington, Texas, nhưng đề nghị Bộ trưởng Phạm Văn Trà ký quyết định cử đoàn ra nước ngoài. Sau chuyến đi ấy, Bộ Quốc phòng ta chính thức tham gia Thỏa thuận đào tạo quân sự quốc tế (IMET- International Military Education Treaty) với Bộ Quốc phòng Mỹ.
Tháng 6/2005, Thủ tướng Phan Văn Khải là nhà Lãnh đạo Cấp cao đầu tiên của Việt Nam thăm Mỹ sau 30 năm kết thúc chiến tranh (1975-2005) và 10 năm bình thường hóa quan hệ giữa hai nước (1995-2005). Thứ trưởng Nguyễn Huy Hiệu là thành viên tham gia đoàn cấp cao này. Đây là chuyến thăm lịch sử đối với đất nước cũng như đối với cá nhân Ông. Quan hệ tốt với Mỹ là một yếu tố quan trọng để hội nhập kinh tế quốc tế và củng cố môi trường hòa bình, ổn định của đất nước. Đến 2005, đặc biệt sau 5 năm thực hiện Hiệp định Thương mại song phương (BTA) và tháng 11/2003, Bộ trưởng Quốc phòng Việt Nam, Phạm Văn Trà đã đến thăm Mỹ lần đầu tiên, tạo đà cho lòng tin của Việt Nam vào triển vọng bang giao với Mỹ, trong đó có quan hệ quốc phòng, mặc dù ảnh hưởng của quá khứ vẫn còn phức tạp đối với cả hai bên. Tướng Hiệu từng là chiến sĩ cầm súng chiến đấu trực tiếp với quân xâm lược Mỹ ở chiến trường phía Nam, bị thường khắp mình, nay lại là người phụ trách mảng đối ngoại quốc phòng, đàm đạo trực tiếp với các nhà chức trách quốc phòng Mỹ để tìm cách vượt qua quá khứ, hàn gắn vết thương chiến tranh, hướng tới tương lai tươi sáng hơn cho nhân dân, quân đội và hai nước. Từ chuyến thăm này, Thủ trưởng Bộ thường được tháp tùng lãnh đạo Đảng, Nhà nước đi thăm các nước, tăng thêm cơ hội mở rộng quan hệ quốc phòng, nâng cao uy tín quân đội.
Tiếp theo chuyến thăm này, năm 2006, Bộ trưởng Quốc phòng Mỹ Đô-nan Răm-xphen (Donald Rumsfeld) thăm chính thức Việt Nam. Năm 2007, Tổng thống Mỹ Bu-sơ (George W. Bush) dỡ bỏ một phần lệnh cấm vận bán các loại trang thiết bị quốc phòng phi sát thương và dịch vụ quốc phòng cho Việt Nam. Tháng 6/2008, một lần nữa, Thượng tướng Nguyễn Huy Hiệu tháp tùng Thủ tướng Nguyễn Tấn Dũng thăm chính thức Mỹ. Hai nước thống nhất tổ chức các cuộc đối thoại an ninh – chiến lược cấp thứ trưởng. Đối thoại đầu tiên được tổ chức vào tháng 10/2008 tại Washington.
Các lĩnh vực hợp tác song phương được mở rộng, trong đó chủ yếu là Mỹ giúp ta đào tạo quân y, phòng chống HIV/AID thông qua chương trình PEPFAR, cứu trợ nhân đạo, hỗ trợ thảm họa, đào tạo tiếng Anh cho hoạt động gìn giữ hòa bình, chia sẻ thông tin, nâng cao năng lực phòng chống khủng bố, an ninh mạng, an ninh nguồn nước, dự báo thời tiết… Cho đến nay, Việt Nam và Mỹ vẫn tiếp tục hợp tác khắc phục hậu quả chiến tranh: đã tổ chức khoảng hơn 4.000 lượt điều tra hỗn hợp với trên 1.000 hài cốt quân nhân mất tích được trao trả cho phía Mỹ; hai bên tiếp tục phối hợp thực hiện tìm kiếm, xác định danh tính những liệt sỹ và bộ đội Việt Nam mất tích trong chiến tranh.
Rõ ràng, ít lâu ngay sau khi bình thường hóa quan hệ ngoại giao với Mỹ, công tác đối ngoại quân sự, quốc phòng Việt Nam với cường quốc lớn nhất thế giới trong hơn 10 năm (từ năm 2000 đến 2011), dưới sự chỉ đạo của Đảng ủy Quân sự Trung ương và trực tiếp chỉ đạo của Thứ trưởng Nguyễn Huy Hiệu đã tạo đà phát triển tốt đẹp cho những bước tiến sau này, khi hai nước đã trở thành đối tác hợp tác toàn diện của nhau.
Thiếu tướng, GS. TS Nguyễn Hồng Quân