Początki królestwa są mało znane. Wydaje się, że Alodia jest w jakiś sposób powiązana z królestwem Meroe, gdyż powstała na terenach będących kolebką tego kuszyckiego państwa. Pierwszym zapiskiem źródłowym może być meroicka stela z okresu panowania Nastasena (335–315/310 p.n.e.), gdzie wymienia się region AlutEl-Din Abdalla Zarroug Mohi, The Kingdom of Alwa, s. 7., który, jak sądzi część badaczy, można identyfikować z ziemiami, na których ukształtowała się Alodia. Pierwszą konkretniejszą wzmianką jest zapis Pliniusza Starszego, który tworząc listę miast nubijskich, umieścił na niej Alwę. Pytanie o związki z Meroe i jego cywilizacją są, jak sądzą niektórzy badacze, kluczowe w dalszych badaniach historii Alodii.
Chrystianizacja
Alodia jako ukształtowane państwo pojawia się przy okazji chrystianizacji ziem między Egiptem a Etiopią, której władcy z królestwa Aksum od IV wieku byli chrześcijanami. Zaraz po nawróceniu Aksum, terenem ożywionej działalności misyjnej stała się Nubia, a działali tu głównie mnisi egipscy. W V wieku oficjalnie doszło do rozłamu chrześcijaństwa wschodniego na tle sporów chrystologicznych. Zwolennicy monofizytyzmu i diofizytyzmu zaczęli się nawzajem zwalczać. Monofizytyzm cieszył się poparciem kościoła egipskiego i tamtejsi duchowni głosili chrześcijaństwo w Nubii przy zachowaniu nauki monofizyckiej.