Calleja is a surname found in Spain (as well as countries people of Hispanic descent) and Malta.
On May 22, 1271, Bertrando de Real, the magister of Malta, was instructed to keep a note of the names and surnames of those who transported the falcons to the royal court from Malta; Martinus Calleya was a witness and Leo Caleya is among those included in the list.
[1] Of note, the persons on the 1271 document belonged to the wealthy class and did not include any serfs or peasants, nor any surnames of Arabic derivation.
[2] Wied il-Qlejgħa (more popularly known as Chadwick Lakes) means the Valley of the Small Castle.
The nearest town to Il-Qlejgħa is Birkirkara, 11.4 km east, which has the highest concentration of people with the surname Calleja.