1898 wurde der Ort unter dem Namen Truxton Canyon gegründet. 1900 kam die zweigeschossige indianische Schule hinzu, wo man den Indianern die Lehren des "Weißen Mannes" unterrichtete, um sie zu "zivilisieren". Der Schuldirektor war gleichzeitig der Postmeister. Als die Schule 1910 kurzzeitig geschlossen war, bedeutete das das gleiche für den Postdienst. 1910 kam es zur Widereröffnung, doch nach einer Postrichtlinie der damaligen Zeit musste der Ort umbenannt werden. So ehrte man Robert G. Valentine, dem Commissioner of Indian Affairs (Beauftragten indianischer Angelegenheiten) und gab dem Ort seinen Namen.

Wegen der damals üblichen "Rassentrennung" wurde noch eine zweite Schule für weiße Kinder erbaut, ironischerweise die "rote Schule" genannt.

Die Post von Valentine hatte stets viel zu tun, waren ihre herzförmigen Poststempel doch sehr beliebt. Heute ist der Ort eine Geisterstadt, die herzförmigen Stempel aber noch in Kingman zu bekommen.