El topónimo es una interesante muestra de la existencia del sustantivo femenino castilleja, evidentemente un derivado secundario del muy frecuente castillejo, a su vez un derivado diminutivo-despectivo de castillo. No sabemos si hubo o no alguna diferencia semántica entre la forma masculina y la femenina. La pareja recuerda otras existentes del mismo tenor como pozo-poza, olmo-olma, lugarejo-lugareja, etc. La frecuencia toponímica de esta forma no es grande y se concentra en un porcentaje muy grande en Andalucía occidental con algún ejemplo aislado en Guadalajara, Cuenca, Valladolid y Cáceres. El segundo elemento del compuesto toponímico es útil en cuanto diferencia esta Castilleja de otras existentes, incluso en la misma provincia, que también tienen un segundo elemento, como Castilleja de la Cuesta, por ejemplo. Este segundo elemento es antiguo, no añadido en fecha reciente.