První písemná zmínka o obci pochází z roku 1167. Nejstarší dějiny Újezda souvisejí s rozsáhlým újezdem „na Lubém“, zmiňovaným v listině krále Vladislava I. pro litomyšlský premonstrátský klášter („circuitum … qui dicitur Nalabnenn“). O újezdu píše také listina vratislavského biskupa Přeclava z Pogorelly z roku 1347, která upravovala majetkové poměry mezi litomyšlským biskupem a tamní kapitulou („Vyesd usque in Chocinow ascendendo“). Touto listinou byl Újezd přidělen litomyšlskému biskupovi až k Chotěnovu se všemi právy, důchody i zástavami.
V roce 1358 postoupil biskup Jan II. ze Středy úrok 100 kop z Újezda a Osíka klášteru ve Zbraslavi, který jej měl do deseti let převést na své bližší statky. Újezd měl být následně vrácen biskupovi, což se patrně stalo, neboť v notářském instrumentu z roku 1398 je obec opět uváděna jako biskupský majetek. V roce 1412 biskup Jan IV. Železný obec osvobodil od odúmrtí.
Po zániku litomyšlské diecéze přešel Újezd do světské držby. V roce 1547 bylo litomyšlské panství v souvislosti s prvním protihabsburským odbojem konfiskováno rodu Kostků z Postupic. Horní Újezd je následně uveden v „Registrech hlavních zámku Litomyšle s jeho příslušenstvím“ z roku 1548. Zmínky o Dolním i Horním Újezdu se objevují také v roce 1654 („ves Dolni Augest … ves Horni Augest“).
S obcí je spjata také osobnost mlynáře Lukáše Pakosty z cikovského Ležákova mlýna, vůdce selského povstání na Litomyšlsku v roce 1680, připomínaného pamětní deskou na mlýně.
