From Chinua Achebe’s Arrow of God:
My purpose in these paragraphs is limited to impressing on all Political Ofﬁcers working among the tribes who lack Natural Rulers the vital necess1ty of developing without any further delay an effecrive system of “indirect rule” based on native institutions.
To many colonial nations native administration means government by white men. You are all aware that H.M.G. considers this policy as mistaken. In place of the alternative of governing directly through Administrative Ofﬁcers there is the other method of trying while we endeavour to purge the native system of its abuses to build a higher civilization upon the soundly rooted native stock that had its foundation in the hearts and minds and thoughts of the people and therefore on which we can more easily build, moulding it and establishing it into lines consonant with modern ideas and higher standards, and yet all the time enlisting the real force 0f
the spirit 0f the people, instead of killing all that out and trying to start afresh.
In the story, this is a letter from a regional British governor.
I first heard the phrase “hearts and minds” from American military leaders during the Afghanistan invasion and occupation. Unconsciously, I thought it originated from that time.
Arrow of God is fictional, but it was written in the 1960s and is set in the late 19th century. It’s possible that Achebe coincidentally came up with the same phrasing, but I think it likely that this is a very old phrase used by colonizers.