The OED shows story as the original form (ante 1400*). The entry’s list of forms implies that storey first came in in the 1600s, but among the citations, the earliest is from 1852, and American (Uncle Tom’s Cabin).
I recognize storey as a British variant, but would only write story.
*However, there is this note: “Quot. a1400, though the reading is app. the scribe’s conjectural emendation of an obscure passage, may perh. be taken as attesting the existence of the n. at the date of the MS.; the passage was prob. supposed to refer to the addition of ‘stories’ or upper stages to towers.”
The next citation (1480) is plural, but spelled storyes.