Under 1180-talet beslöt ärkebiskop Absalon i Lund att det skulle byggas en ny kyrka. Att kyrkan skulle byggas precis på kullen i Östra Sallerup kan ha berott på att biskopen ägde flera hemman i trakten och just vid 1100-talets mitt stod Lunds domkyrka klar och många arbetare inom området stod nu arbetslösa. En stenkyrka med tjocka murar och högt sittande små fönster vara även bra ur ett militäriskt syfte. I orostid skulle den kunna ge skydd åt både traktens folk och de lokala soldaterna.
Precis som många andra kyrkor så har Östra Sallerups kyrka byggts ut i omgångar allt eftersom församlingen expanderat. 1745 slogs väggen mellan tornet och kyrkan ner för att skapa mer utrymme. 1864 behövdes mer plats och en tillbyggnad åt söder uppfördes för att få plats med fler bänkar. 1896 behövde man ännu mer plats och ett beslut togs att ta bygga en läktare i den södra tillbyggnaden. På läktaren gjorde man också plats för kyrkans första orgel.
Vid en restaurering 1935-36 fick kyrkan nya fönster. Bl.a. det färgrika altarfönstret skapat av Hugo Gelin. Bilden föreställer Kristus med uppsträckta välsignande händer. Bilden är inramad med texten "Gud vare tack som giver oss seger genom vår Herre Jesus Kristus" och under Kristus står "Jag lever I skolen ock leva"
På 1960-talet gjordes en större renovering. Taket fick en nya klädsel av furu. Läktaren togs bort, orgeln fick sin plats nere i kyrkorummet, altare och altarskrank byttes och kyrkan fick ett nytt tegelgolv. Dopfunten som är jämngammal med kyrkan, fick sin nya plats till höger om altaret.
Ett vapenhus byggdes på den södra utbyggnaden. När fundamentet skulle gjutas hittades en murad grav med tillhörande monument. Det var graven av Kyrkoherde Jöns Henrikssons (1622-1689) och monumentet han rest över sig själv. Graven hade "legat i vägen" när man 1864 skulle bygga trappan till sidoskeppet. Allting ovan jord revs då bort. Delar av monumentet placerades i kyrkomuren och resten grävdes ner. Delar av monumentet, som hade formen av en stor stenkista, kan numera beskådas på kyrkans norra sida.
Under 1400-talet försågs innertaket med valv. Vid 1700-talets mitt revs västgaveln. Kyrktornet som tidigare varit fristående byggdes då ihop med kyrkan. En korsarm i söder tillkom 1864.