הישוב הראשון במקום של מאלקו טרנובו בת ימינו היה תראקי. בתקופת הקיסר הביזנטי קונסטנטינוס האזור התפתח תרבותית וכלכלית בזכות קרבתו לבירת האימפריה הרומית המערבית - קונסטנטינופול. העיר הנוכחית הוקמה בסוף המאה ה-16 ותחילת המאה ה-17. מאלקו טרנובו ממוקמת בלב הרי סטראנג'ה, באחד מאזורי היערות השמורים ביותר בבולגריה עם אקלים ייחודי ומגוון עשיר של מיני צמחים ובעלי חיים. בעיר והסביבה ניתן למצוא הרבה אתרים ארכאולוגיים חשובים הקשורים לתראקים. מספר חוקרים מוכרים טוענים שבמקום קיים יישוב כבר בעת העתיקה, על כך מעידים ממצאים מתקופות שונות. שני תלי הקבורה התראקיים בקרבת העיר מרתקים את המבקרים. הם נבנו עם אבני שיש מעובדים היטב, המציגים את אמנות הבניה המונומנטלית של התראקים מהמאה ה-5 עד למאה ה-3 לפנה"ס ואת מסורת הקבורה של האצילים.