Хотя Аргостоли считается относительно молодым по античным меркам городом, окружающая его территория хранит следы пребывания человека еще с эпохи палеолита. В древности этот регион был частью кефалонийского тетраполиса и был тесно связан с античным полисом Крани, руины которого и сегодня свидетельствуют о величии микенской цивилизации.
Современная история поселения как административного центра началась в 1757 году. Именно тогда венецианские власти приняли решение перенести столицу острова Кефалония из защищенного, но неудобного для торговли замка Агиос Георгиос (Кастро) на берег бухты. Главным фактором становления города стала его уникальная естественная гавань, считающаяся одной из самых безопасных в Греции.
Ранний период развития города был неразрывно связан с морской торговлей и постепенным формированием портовой инфраструктуры. Этимология названия Аргостоли до сих пор вызывает дискуссии среди историков: одни связывают его с греческим морским термином, обозначающим медленную стоянку флота, другие — с фамилией влиятельных местных землевладельцев.