Allinge og Sandvig er opstået som fiskerlejer, der i senmiddelalderen tiltrak købmænd fra Danzig, Elbing og andre hansestæder, som ønskede at få del i Østersøens sildeeventyr. Allinge og Sandvig nævnes i flere kilder fra perioden 1393‑1433, hvor der bl.a. omtales flere strandinger ved Sandvig. Formentlig har byerne allerede i middelalderen også tjent som færgesteder ved overfart til Skåne.
Selv om Allinge og Sandvig tilsyneladende aldrig har fået købstadsrettigheder, blev de senest fra slutningen af 1700-tallet reelt betragtet som købstæder.
Ved den store pestepidemi i 1618 omkom 126 personer i de to byer; ved epidemien i 1654 var antallet 102. I 1769 havde Allinge og Sandvig hhv. 303 og 218 beboere, og de var dermed to af landets absolut mindste købstæder. I 1801 var deres samlede befolkningstal vokset til 585 og i 1855 til 871.
Væksten fortsatte i anden halvdel af 1800-tallet. I 1870 havde byerne 1.022 indbyggere, i 1890 var tallet 1.838, og i 1901 var antallet af indbyggere 2.709. Herefter skete der imidlertid et drastisk fald, og i 1921 boede der 1.864 i de to byer, heraf ca. tre fjerdedele i Allinge. Fremgangen sidst i 1800-tallet skyldtes især en betydelig ekspansion i den lokale råstofudnyttelse. Mens Allinge i 1872 havde to granitbrud med i alt ca. 20 ansatte, rummede byen i 1899 – ud over en række mindre industrier – fire stenhuggerier med tilsammen ca. 200 arbejdere, og på Hammeren havde Bornholms Granitværk ca. 350 mand i arbejde. En stor del af dem stammede fra Sverige, og mange af dem har formentlig søgt væk fra stedet, efter at Bornholms Granitværk lukkede i 1916. Nedgangen i befolkningstallet i 1910’erne hænger dog også sammen med, at den store tilstrømning af tyske sommerturister, som havde præget området i flere årtier og givet beskæftigelse til mange beboere, ophørte ved 1. Verdenskrigs udbrud.
Både Allinge og Sandvig fik deres første havneanlæg i første halvdel af 1800-tallet, og i Allinge skete der væsentlige havneforbedringer 1856‑62, i 1870’erne (efter stormfloden i 1872) og 1914‑19. Begge byer blev forsynet med en station i forbindelse med etableringen af Rønne-Sandvig-banen i 1913. Af vigtige nye bygninger fra perioden 1870‑1920 kan bl.a. nævnes råd-, ting- og arresthuset (Allinge, 1881), en borgerskole i hver af byerne (1890 og 1893), teknisk skole (Allinge, 1895), sygehuset (Allinge, 1909), syv missionshuse og kapeller, heraf fem i Allinge (1875‑1918), samt en række hoteller.
I 1925 var Allinges og Sandvigs samlede befolkningstal steget til 2.274. Tallet holdt sig nogenlunde på dette niveau i det næste par årtier, og i 1950 blev der registreret 2.189 indbyggere. I 1970 var det imidlertid faldet til 1.991. Stenbrudsarbejdet ved Hammershus fortsatte indtil begyndelsen af 1970’erne. Allinge og Sandvig nød også godt af et stigende antal turister fra og med 1930’erne. Derudover havde byerne stadig en del mindre håndværks- og industrivirksomheder; i 1948 var der fx 87 virksomheder med i alt 441 ansatte.
Rådhuset i den nye Allinge-Gudhjem Kommune, dannet efter Kommunalreformen i 1970, blev anbragt i Tejn. Nedgangen i befolkningstallet er fortsat siden 1970, og i 1994 havde Allinge og Sandvig således i alt 1.907 indbyggere. Fiskeriet blev også stærkt reduceret, hvorimod turismesektoren fortsatte med at vokse.
