Anticamente, Sestino fu una roccaforte del periodo romano, successivamente trasformata in un castello che andò distrutto. Plinio ricorda la battaglia di Sestino del 295 a.C., condotta dal console Fabio Massimo contro i Galli Senoni, alleati con gli Umbri e la Lega Etrusca.
Nella località sono stati ritrovati reperti romani e resti di strutture termali. Nella zona, precisamente nella Fossa della Selva, sgorga una polla di acqua salata a 16 gradi, utilizzata in passato per curare malattie tubercolari infantili.
Sestino rimase sotto il controllo della Santa Sede fino al 1516, quando la diocesi di Montefeltro, gravata da un debito con la Repubblica di Firenze, fu costretta a cederla a quest’ultima su ordine di Papa Leone X. Insieme a Sestino, furono cedute anche le fortezze di San Leo e Maiolo. Alla morte di Leone X, il Duca di Urbino, Francesco della Rovere, riuscì a recuperare San Leo e Maiolo, ma non Sestino, dove fu inviato il commissario fiorentino Francesco Vettori.
Nel 1536, un gruppo di fuoriusciti fiorentini, guidati da Piero Strozzi, nobile della famiglia patrizia degli Strozzi e naturalizzato francese, tentò di conquistare Borgo Sansepolcro. Tuttavia, a Sestino furono respinti per la troppa fretta di entrare dentro le mura.
Da quel momento, Sestino rimase sotto il Granducato di Toscana e, successivamente, entrò a far parte della provincia di Arezzo.
