Iespējams, Volina ir viena no senākajam pilsētām reģionā, jo tiek saistīta ar vikingu pilsētas Jomsborgas un Vinetas atrašanās vietu. Ādams no Brēmenes aprakstījis Jomsborgu kā vienu lielākajām Eiropas pilsētām. Līdz XII gadsimta beigām dāņu uzbrukumos pilsēta tika nopostīta. Vācu kolonizēšanas laikā tika nodibināta jauna pilsēta, kurai 1260. gadā tika piešķirtas Lībekas tiesības.
Volinā līdz apmēram 1150. gadam atradās pirmā reģiona bīskapa rezidence, pēc tam pārvietota uz Uzedomas abatiju, bet vēlāk, līdz reformācijas uzvarai 1544. gadā, bīskapa rezidence atradās Kamminā.
Līdz Otrā pasaules kara beigām pilsēta atradās Vācijā, un tās vāciskais nosaukums bija Vollina (vācu: Wollin). Pēc Otrā pasaules kara pilsētas vācu iedzīvotāji tika padzīti, bet vietā ieradās poļi no PSRS ieņemtajiem Polijas apgabaliem.