Legenda głosi, że Budva została założona przez Kadmosa, fenickiego herosa wydalonego z Teb, który znalazł tu schronienie dla siebie i swojej żony, Harmonii[1]. Zgodnie z ustaleniami archeologów, wpierw (od IV w. p.n.e.) istniała tu jednak osada iliryjska, później dopiero kolonia grecka Buthoe[2]. W 168 r. p.n.e. miasto wraz z całą okolicą zostaje przejęte przez Rzym. Za czasów rzymskich, nosiło nazwę Butua i było częścią prowincji Illyricum (w czasach Republiki), a później Dalmatia (w czasach Cesarstwa). Wówczas rozwinął się handel oraz uprawa winorośli i oliwy. Największy rozkwit miasta przypadał na I i II wiek n.e.[2] Po upadku Cesarstwa Rzymskiego i jego podziale na Wschód i Zachód, miasto leżało w obszarze granicznym obu potęg[3], co wywarło wpływ na jego historię i kulturę. We wczesnym średniowieczu miasto znalazło się pod rządami Cesarstwa Bizantyńskiego. Wówczas także wraz z Awarami przybywają tu pierwsi Słowianie. Na przełomie XII i XIII w. Budva podlegała książętom Duklji, a później Zety. Swój największy rozkwit w średniowieczu Budva uzyskała w XIV wieku, w czasie panowanie króla i cara serbskiego Stefana Urosza IV Duszana[1].

Od 1422 r. Budva (wówczas zwana w języku weneckim Budua) należała do Republiki Weneckiej, jako część tzw. Albanii Weneckiej. Wówczas miasto zostało ufortyfikowane murami, aby chronić je przed najazdami osmańskimi. W 1667 r. zostało znacznie zniszczone przez silne trzęsienie ziemi[4]. Miasto wraz z okolicami aż do początków XVIII w. musiało liczyć się z wieloma walkami, jakie prowadzili wówczas Turcy i Wenecjanie o kontrolę nad regionem. Zgodnie z informacjami historyka Luigi Paulucci w jego książce „Le Bocche di Cattaro nel 1810” (Zatoka Kotorska w 1810), większość mieszkańców mówiła wtedy językiem weneckim aż do początków XIX w. Jeden z najwybitniejszych kompozytorów i librecistów teatru, Cristoforo Ivanovich, urodził się w weneckiej Budua.

Po upadku Republiki Weneckiej i pokoju w Campo Formio w 1797 r., Budva (wraz z całym regionem) stała się częścią Monarchii Habsburgów. W ciągu następnych kilkunastu lat epoki napoleońskiej miasto zajmowały różne wojska, wpierw francuskie, później rosyjskie, potem ponownie francuskie. Po Kongresie wiedeńskim w 1815 r. Budva (wraz z całym regionem) stała się częścią Królestwa Dalmacji, będącego krajem koronnym Cesarstwa Austrii. Po zakończeniu I wojny światowej miasto stało się częścią nowo powstałego Państwa Słoweńców, Chorwatów i Serbów, przekształconego miesiąc później w Królestwo Serbów, Chorwatów i Słoweńców, a od 1929 pod nazwą Królestwo Jugosławii. Podczas włoskiej okupacji w latach 1941–1943 miasto było częścią Prowincji Kotorskiej (Provincia di Cattaro), jednej z trzech prowincji w Gubernatorstwie Dalmacji. Oswobodzenie miasta z rąk nazistów miało miejsce 22 listopada 1944 r.[1] Po zakończeniu II wojny światowej Budva weszła w skład Socjalistycznej Republiki Czarnogóry, będącej częścią składową tzw. drugiej Jugosławii. W latach 1992–2003 wchodzi w skład Federalnej Republiki Jugosławii, a później w latach 2003–2006 Serbii i Czarnogóry.

Podczas trzęsienia ziemi w kwietniu 1979 r. miasteczko zostało poważnie uszkodzone, a wstęp do starej części miasta był przez pewien czas zabroniony[4]. Zniszczenia z czasem odbudowano i dziś nie ma po nich śladu.