Old English æt, from Proto-Germanic *at (cf. Old Norse, Gothic at, Old Frisian et, Old High German az), from PIE *ad- "to, near, at" (cf. Latin ad "to, toward" Sanskrit adhi "near;" see ad-).
Lost in German and Dutch, which use their equivalent of to; in Scandinavian, however, to has been lost and at fills its place. In choosing between at church, in church, etc. at is properly distinguished from in or on by involving some practical connection; a worshipper is at church; a tourist is in the church.
The colloquial use of at after where ("where it's at") is attested from 1859. At last is recorded from late 13c.; adverbial phrase at least was in use by 1775. At in Middle English was used freely with prepositions (e.g. at after, which is in Shakespeare), but this has faded with the exception of at about, which was used in modern times by Trollope, Virginia Woolfe, D.H. Lawrence, and Evelyn Waugh, but nonetheless is regarded as a sign of incompetent writing by my copy editor bosses.