Brian Hitchcock is right that both are possible and could be understood the same way.
Here are a couple of real examples:
False at heart:
She said that he was false at heart,
He called her light coquette :
And both exclaimed--"next week we part,
I wish we ne'er had met."
—The New English Drama: With Prefactory Remarks, Biographical Sketches, and Notes, Critical and Explanatory
Volume 19, edited by William Oxberry.
False of heart:
O, never say that I was false of heart,
Though absence seem'd my flame to qualify.
As easy might I from myself depart
As from my soul, which in thy breast doth lie.
—Shakespeare's Sonnets, edited, with notes by William J. Rolfe. Litt.D., 1883.
(The Sonnets were first published in 1609.)