late 14c., from amidde (c. 1200), from Old English on middan "in the middle," from dative singular of midde "mid, middle" (from PIE root *medhyo- "middle"); also see a- (1). The phrase evidently was felt as "in (the) middle" and thus followed by a genitive case, and if this had endured we would follow it today with of. (See amidst for further evolution along this line).
The same applies to equivalents in Latin (in medio) and Greek (en meso), both originally adjective phrases which evolved to take the genitive case. But in later Old English on middan also was treated as a preposition and followed by dative. Used in compounds from early 13c.