მუშთაიდის ბაღის ისტორია სევდიან და ამავდროულად რომანტიკულ სიყვარულის ისტორიას უკავშირდება, რომელსაც ისტორიკოსები ჯერ ვერ ადასტურებენ, თუმცა არც უარყოფენ. ისტორიის დასაზუსტებლად კვლევა დღემდე მიმდინარეობს.
გადმოცემის თანახმად, ბაღი თბილისში, მე-19 საუკუნეში გაშენდა, ირანელი დიდგვაროვანის მიერ. სწორედ მისი გვარია მუშთაიდი, რაც შემდეგ ბაღს ეწოდა.
მუშთაიდის ცოლი ქართველი ქალი იყო, ნინო, რომელიც ირანელმა დიდგვაროვანმა სტამბულის ტყვეთა ბაზარზე იყიდა. საყვარელი ცოლის თხოვნით მუშთაიდი თბილისში გადმოვიდა საცხოვრებლად, თუმცა მეუღლე მალევე გარდაეცვალა. ირანელმა დიდგვაროვანმა ნინო სახლის წინ დაკრძალა და მის საფლავზე ვარდები დარგო. თანდათან მუშთაიდმა საფლავის გარშემო ბაღი გააშენა, რომლის მოსარწყავად არხი მტკვრიდან გადმოიყვანა.
მოგვიანებით მუშთაიდი სამშობლოში დაბრუნდა, ბაღი კი ერთ-ერთ ვაჭარს მიჰყიდა. დროთა განმავლობაში ბაღი სასეირნო და გასართობ ადგილად იქცა. სწორედ მუშთაიდის ბაღში გაიხსნა მსოფლიოში პირველი საბავშვო რკინიგზა.
მუშთაიდის ბაღში ათასობით ჯიშის უნიკალური მცენარეა გაშენებული (გლედიჩია, თელა, იფანი, საპნის ხე, ქაღალდის ხე, თუთა, ელდარის ფიჭვი, კედარი, გუნდის ხე, მრავალი ბუჩქი და ყვავილი).
მიუხედავად იმისა, რომ ბაღმა რამდენჯერმე გამოიცვალა სახელი, მათ შორის ერთი პერიოდი მას ორჯონიკიძის ბაღს უწოდებდნენ, მაინც სამუდამოდ შერჩა დამაარსებლის, მუშთაიდის სახელი, ირანელი დიდგვაროვანის შემოქმედებაზე ქართველების მადლიერების ნიშნად.