Područje Gajdobre je naseljeno još od neolita. Prvi put se pominje 1464. godine, pod imenom Dobra. Isto mesto se spominje i 1554. godine, kao naselja „Gornja Dobra“ i „Donja Dobra“, koja su naseljena uglavnom Srbima.
Početkom 1702. godine, Gajdobra se pominje kao novo naselje sa dva srpska domaćinstva koja plaćaju porez. Gajdobra je 1715. godine imala pet srpskih domaćinstava, pet godina kasnije, u Gajdobri živi šest porodica: Stojić Mali, Koja Sremac, Radujša Sremac, Milisav Radojčin, Mileta Bančinin i Radoviša Banjalučanin. Tokom 1728. godine u Gajdobri je popisano osam srpskih porodica: Stojko Ladislav, Stojić Mali, Milisav Ivanković, Ostoja Pivničanin, Nikola Stojić, Mileta Gajdobranin, Ivan Živković, Todor Posin, Milisav Dobričanin i Stojić Vladislav.
Za vreme vladavine austrijske carice Marije Terezije i njenog sina Josifa II, Nemci (Švabe) naseljavaju prostor Vojvodine. Nemci naseljavaju Gajodbru 1763. godine, gde 1791. godine grade Crkvu Sv. Martina koja i danas postoji (obnovljena 1897. godine). Prvi nemački doseljenici su prvih 10 godina bili oslobođeni plaćanja poreza, nakon toga su plaćali porez nazvan Urbario.
Godine 1848. Gajdobru je pogodila epidemija kolere. Na sastanku koji je održan 15. juna 1848. godine, mađarske vlasti su zahtevale da im Opština Gajdobra uputi 15 zaprežnih kola za prevoz ratnog materijala i ostalih stvari za rat. Zaprežna kola sa vozačima su se zadržala na terenu sve do kraja juna, ni ne sluteći kakvu će pošast doneti u Gajdobru. Neki od vozača će umreti od kolere u Pirošu (Rumenka), neki će biti doneti u sanducima u Gajdobru, a neki bolesni i kao kliconoše će ipak uspeti da dođu u Gajdobru. Na ovaj način cela Gajdobra se našla u zagljaju opake bolesti. Prva žrtva kolere u Gajdobri registrovana je je 1. jula 1848. godine. Epidemija kolere je trajala 7 nedelja i za to vreme odnela 268 života. Najviše umrlih u jednom danu bilo je 28. jula i tog dana je umrlo 16 ljudi. Poslednji slučaj smrti od kolere zabeležen je 31. avgusta, posle koga je život u Gajdobri počeo da se normalizuje. Za vreme epidemije kolere Gajdobra je bila u potpunosti odsečena od sveta. U selo nije moglo ni da se uđe, a ni da se izađe iz njega.
Vrlo je važno istaći da je dolazak Nemaca u Gajdobru uslovio njen privredni razvoj. Godine 1884. osnovan je prvi parni mlin. Osnivači su bili Johan Rajs i Anton Sedreši. U početku je za mlevenje žita korišćena snaga konja koji su se kretali kružnom stazom iza samog mlina i na taj način pokretali valjke za mlevenje. Konji su kasnije zamenjeni sa parnom vršalicom-samohotkom snage 8 KS. Mlin se modernizuje 1891. godine sa novim mašinama i u to vreme je imao kapacitet prerade 1000 kg pšenice za 24 sata.
Preko puta vulkanizerske radnje u Ulici Mira Popare, nalazi se oronula zgrada Rajsovog mlina. Godine 1910. osnovan je Spisov mlin, pokretan pomoću pare. Osnovali su ga braća Danijel i Karl Spis, koji su došli iz Crvenke. Takođe braća su vršila popravke svih vrsta parnih mašina i mašina za vršidbu žita i motora. Zbog povoljnog položaja u odnosu na železnicu, kao i zbog veoma kvalitetnog rada, mlin je postao poznat i cenjen, ne samo u Gajdobri, već i u široj okolini. Braća su se bavila i proizvodnjom vršalica, čije su drvene delove proizvodili u svojoj radionici, a metalne delove su dobavljali iz Nemačke. U dvorištu porodične kuće su imali veliku kovačnicu, najveću u Gajdobri. O veličini kovačnice govori i podatak: sredinom 1960-ih godinam ona je srušena, a cigla od kovačnice je korišćena za izgradnju tri prizemne kuće u Gajdobri.
Vinski klub u Gajdobri je osnovan 6. decembra 1903. godine. Za svrhu izgradnje vinograda odvojeno je 30 jutara zemlje u blizini naselja koja je data u zakup na 30 godina. Takođe, svaki član kluba je dobio na korišćenje 375 hvati zemlje (nešto manje od četvrtine jutra. U vinogradu su bile zastupljene američke sorte vinove loze koje su kalemljene sa lokalnim autohtonim vrstama. U početnim godinama vinograd je dobro rađao, međutim kasnije su se zaređale razne prirodne nepogode koje su usporile razvoj vinograda. Vinski klub je imao direktora i 10 članova pomoćnog osoblja.
Nemci su u Gajdobri ostali do 1944. godine, kada se vraćaju u Nemačku, a u Gajdobru se naseljavaju Srbi iz Bosne i Hercegovine. Krajem 1990-ih gradi se pravoslavna Crkva Sv. Petra.
Pogledaj: Stare mape Bačke Palanke kao svedoci istorije
