Dit fort aan de oevers van de Verde River werd voor het eerst bemand in 1865. Na de dood van president Lincoln heette het een tijdje Camp Lincoln, maar in 1868 bleken er zoveel van dit soort namen te zijn dat om verwarring te voorkomen voor Fort Verde werd gekozen. Dit was de tijd dat Arizona volop werd ontwikkeld door een toenemend aantal pioniers en al snel bleek het fort te klein. Bovendien bleek het niet zo slim te zijn geweest om aan de oevers van de rivier te gaan zitten, aangezien het een broeinest was voor malaria (toen de intermittent fever genoemd). In 1870 verplaatste het leger Fort Verde naar een hogere, bredere plek aan de westelijke oever van de Verde. Daar waait het bijna permanent, zodat de vlag klappert.

Wat er nu nog staat in Fort Verde dateert uit 1871. Toen bouwde het leger 22 gebouwen op een grasvlakte, met in het midden een kaal veld om te marcheren. Het fort werd een belangrijke post in de oorlog tegen de Indianen, onder meer in de zogenoemde Winter Campaign van 1872-73 onder generaal George Crook. Maar de soldaten moesten over het algemeen meer werk verrichten met hun schop en pikhouweel dan met hun geweer.

Er zijn nog vier originele gebouwen over, waaronder het huis van de commandant, dat voor de officieren en dat van de dokter. In wat later de school werd voor het dorp om het fort heen, is een aardige tentoonstelling ingericht.

Dit soort forten werd nooit aangevallen, dus het hoefde ook niet bijzonder beschermd te zijn – de belegerde forten zijn een uitvinding van Hollywood. Het leven van een soldaat bestond vooral uit het verdrijven van de verveling. Ook de trips naar saloons in nabijgelegen dorpen zijn een verzinsel van de film – op ongeoorloofde afwezigheid stond de doodstraf. Deze soldaten kwamen maar heel zelden bij Mrs. Horn’s Saloon, een paar kilometer verderop (ze verkocht waarschijnlijk ook andere behoeften voor eenzame soldaten).