Hay un pequeño lago al suroeste del pueblo, junto al cual se alza una pequeña colina, a menudo llamada "Colina de la Iglesia" por los locales. No obstante, hoy en día no hay iglesia en este lugar, pero sí algunos restos de un asentamiento medieval, entre ellos los cimientos de un edificio más grande, que probablemente fue la iglesia del asentamiento medieval llamado Kalyb.

Kalyb, es decir, la actual Kelebija, fue mencionada por primera vez en 1297 como propiedad de Simon Filins Wasa de Kelyb, un aristócrata del Reino de Hungría.

El pueblo quedó destruido y despoblado durante la ocupación otomana de la región.

En 1702, el territorio de la aldea abandonada (puszta en húngaro) pasó a formar parte de Subotica, el asentamiento más grande de la región en ese momento.

Según un mapa dibujado en 1783, por el terriotorio de la actual Kelebija cruzaban muchas carreteras importantes que salían de Subotica hacia Baja, Bácsalmás, Tataháza, Mátéháza, Mélykút y Kiskunhalas. A lo largo de estas carreteras muchas personas se asentaron formando varias hileras de casas. Estas filas de casas de campo se llaman sor en idioma húngaro, y desde el siglo XIX muchas de las partes relativamente distantes del territorio de Kelebia se han llamado sor con diferentes nombres: Akasztai sor (fila de Akasztai), Belső sor (fila interior), Csajkás sor (la fila de los hombres trabajadores), Kertész sor (la fila del jardinero), Kernyájszky sor (fila de Kernyájszky). Esta última designación indica el nombre de un hombre rico que tenía varios sirvientes que vivían no muy lejos de su villa. Es interesante notar esto, porque la hilera de casas de Kernyájszky a menudo también se llama Szerb sor en lengua húngara, probablemente haciendo referencia al origen étnico (szerb significa serbio) de los habitantes de esta parte de Kelebija.

Kelebija se formó como un pueblo en el siglo XX, cuando se construyó una monumental iglesia católica en 1937 para los numerosos fieles que vivían dispersos por la región. La iglesia sirvió como punto de encuentro y muchos comenzaron a construir sus viviendas alrededor de ella, formando así el centro del pueblo.

Tras la Primera Guerra Mundial, Kelebija pasó a formar parte del recién formado Reino de los Serbios, Croatas y Eslovenos (posteriormente Yugoslavia). Una parte del territorio de Kelebija, que tradicionalmente pertenecía a la aldea, permaneció en Hungría, formándose así un nuevo asentamiento al otro lado de la frontera, que lleva el mismo nombre, pero con la ortografía húngara de Kelebia. Por ello, los húngaros suelen llamar a Kelebija Alsókelebia, es decir, Baja Kelebija. Kelebija volvió a estar bajo el dominio húngaro entre 1941 y 1944 durante la Segunda Guerra Mundial.

En 1978 se abrió el paso fronterizo entre Yugoslavia y Hungría, poniendo así fin al relativo aislamiento del pueblo del resto del mundo.

Hoy en día, Kelebija es el asentamiento más septentrional de Serbia, a unos cientos de metros de la frontera con Hungría.

Según el censo de 2022, el pueblo tiene 1 969 habitantes.

• 1961: 2 974
• 1971: 2 434
• 1981: 1 995
• 1991: 1 975
• 2002: 2 168
• 2011: 2 132
• 2022: 1 969

La composición étnica del pueblo es la siguiente (censo de 2002):

• Húngaros = 1.275 (58,81%)
• Serbios = 367 (16,93%)
• Croatas = 138 (6,37%)
• Bunjevci = 133 (6,14%)
• Yugoslavos = 102 (4,71%)
• Otros

• Slobodan Ćurčić, Broj stanovnika Vojvodine, Novi Sad, 1996.