1297-ből való dokumentum említést tesz egy településről, „Sima, sin Vase, iz Kelyb-a", azonban csupán ez az egy irat alapján nehezen bizonyítható, hogy Kelebiáról van szó. A feljegyzések szerint több mint egy évszázaddal idősebb Szabadkánál.

Az összeállított nyilvántartás szerint (1543) Kelebia település lakói kunok voltak. Az 1572-es írásos jegyzetek alapján Kelebiát már szerbek lakták, hasonlóképp mint Tompát és Ludast. Az 1580-as években 18 adóköteles ház állt Kelebián, míg 1590-91-re a házak száma 57-re nőtt.

A török megszállás ideje alatt ez a falu is elnéptelenedett, és kihalt területként Szabadkához csatolták. Kelebia a XVIII. század közepétől egyike a szabadkai pusztáknak, melyek később Maria Theresiopolis szabad királyi városhoz tartoztak.

A régi templom maradványai a XVIII. század közepén még léteztek és ennek a pusztának az egyik részét Templomhegynek hívták. Ezen a pusztán terült el báró Redl Béla nagy birtoka, amely a maga 2279 kataszteri holdjával a legnagyobbnak számított  a szabadkai határban. A báró 1863-ban egy kápolnát építtetett, utódai pedig 1905-ben felépíttették a káprázatos gótikus stílusú templomot. Ezen a vidéken számos szőlőskert és gyümölcsös terült el, amelyeket a Kelebiai-tó köré telepítettek. A szabadkaiak egyik kedvenc kirándulóhelye volt.

Az 1880-as népesség-összeírás adatai szerint Kelebiának 3738 lakosa volt, legnépesebbek a magyarok voltak, majd  a bunyevácok, szerbek és  a németek. Az akkori időben épült Budapest-Zimony  vasútvonalat az ottani lakosság nem tudta használni, mivel a szerelvények nem álltak meg a Redl Béla által építtetett vasútállomáson. A kelebiai állomáson áthaladó vonatok csak 1897-től kezdtek megállni. Ezen az útvonalon haladt a híres Orient Express is.

A trianoni békeszerződés az eddigi kis térséget kéttéválasztotta, Alsó- és Felső Kelebiára. A délebbre nyúló részt a Szerb-Horvát-Szlovén Királysághoz (későbbi Jugoszláviához) csatolták, jelenleg Szerbia legészakibb települése.