El nombre "Lemba" puede originarse de chilemba, una palabra suajili para turbante usado por algunas gentes bantú o lemba, una palabra bantú en el sentido de que "no son africanos" o "extranjeros respetables".
Aunque hablan lenguas bantúes similares a las de sus pueblos vecinos, los lembas tienen ciertas prácticas específicas, así como sus creencias religiosas aparentan similitudes a las practicadas dentro del judaísmo, que se cree son de tradición popular, habiéndose recordado y transmitido principalmente a través de la tradición oral entre las sucesivas generaciones del pueblo lemba.
Otra posibilidad es que Sena se refiriera al puerto portugués fundado a orillas del río Zambezi a fines del siglo XVI por "cristianos nuevos" (judíos conversos) de Portugal.
Varias pruebas genéticas apoyan y corroboran las tradiciones orales transmitidas entre sus congéneres por los lembas, quienes se originaron muy probablemente en el sur del Oriente Medio.
2011) observó una frecuencia moderadamente alta de las muestras del ADN estudiado entre las muestras aportadas por los lembas que llevaban el haplogrupo T (ADN-Y), del cual se afirma a su vez que se originó en el Oriente Medio.
Se ha observado T1b en bajas frecuencias entre los búlgaros y solamente entre las poblaciones askenazíes, así como entre pocos individuos de los pueblos levantinos.
El investigador sugiere que el parentesco genético se deba tal vez a "una fuerte conexión con los pueblos del Oriente Medio, probablemente como resultado de su actividad comercial en el Índico".