ניקולאי מלאדנוב נולד בסופיה. הוא רכש השכלה אקדמית בסופיה ובלונדון. ב-2001 נבחר לפרלמנט הבולגרי מטעם "איחוד הכוחות הדמוקרטיים" בהנהגת איוואן קוסטוב. ב-2005 פרש מהמפלגה. ב-2007 הצטרף למפלגת "אזרחים למען פיתוח אירופי של בולגריה" ונבחר מטעמה לפרלמנט האירופי. בהמשך כיהן כשר ההגנה בממשלו הראשון של בויקו בוריסוב, וב-2010 התמנה לשר החוץ של בולגריה. בתקופת כהונתו כשר החוץ חלה התקרבות נוספת ביחסי ישראל ובולגריה. בספטמבר2011, בעת ביקור באנקרה, הביע ניקולאי מלאדנוב הסתייגות מקווי מדיניותה של טורקיה כלפי ישראל בעקבות אירועי המשט לעזה.[2]
במרץ 2013 התפטרה ממשלתו של בוריסוב. ב-2 באוגוסט 2013 מונה מלאדנוב לשליח האו"ם לעיראק.