This paper addresses the genesis of Nubi, an Arabic-based creole, spoken in Uganda and Kenya. A novel account is offered using the relexification approach (Lefebvre, 1998, 2009). The study tests the hypothesis that the genesis of Arabic-based creole, Nubi can best be accounted for using the cognitive processes of relexification and dialect levelling. The two major cognitive processes of relexification and dialect levelling are shown to have played a major role in the genesis of Nubi. It is demonstrated that the phonological form of Nubi lexical items is derived from Sudanese Arabic, the superstrate language. Following Wellens (2003), a subset of the languages that exercised a substrate influence on the development of Nubi is considered. The cognitive processes of relexification and dialect levelling are shown to have played a major role in the genesis of Nubi minor category possessive forms and negative markers. The same processes are also shown to have played a major role in the genesis of Nubi major category personal pronouns. The word order of Nubi lexical items shows the following pattern: minor category lexical items (the definite article, the demonstrative determiner, and cardinal numerals) follow the word order of some of the substrate languages (Nuba, Kunuz Nubian, Acholi and Ma’di), but major category lexical items (adpositions, attributive adjectives, lexical verbs, and adverbs) follow the word order of the superstrate language. The results of the study lend support to the hypothesis that the genesis of Nubi can best be accounted for using the cognitive processes of relexification and dialect levelling.