Štarnberga pirmoreiz rakstiskos avotos minēta 1226. gadā. Vairākus gadsimtus tā bija vienīgi vietējo grāfu oficiālais sēdeklis un tikai 19. gadsimtā Štarnberga sāka attīstīties par vērā ņemamu apdzīvotu vietu. Pirms Štarnberga ieguva savu pašreizējo nosaukumu, tā daudzu gadsimtu garumā tika dēvēta par Aheimu pie Virmzē (vācu: Aheim am Würmsee). 1854. gadā tika atklāts Minhenes—Štarnbergas dzelzceļš un bijušais zvejnieku ciematiņš pamazām sāka pārvērsties par iecienītu Minhenes vasarnīcu un rezidenču rajonu. 1912. gadā Štarnberga ieguva pilsētas tiesības.