Among recurrent sanitary emergencies able to spread rapidly worldwide, avian influenza is one of the main constraints for animal health and food security. In West Africa, Nigeria has been experiencing repeated outbreaks of different strains of avian influenza virus (AIV) since 2006 and is also recognized as a hotspot in the region for the introduction of emerging strains by migratory wild birds. Here, we generated complete genomes of 20 highly pathogenic avian influenza (HPAI) H5N8 viruses collected during active surveillance in Nigerian live bird markets (LBM) and from outbreaks reported in the country between 2016 and 2019. Phylogenetic analysis reveals that the Nigerian viruses cluster into four separate genetic groups within HPAI H5 clade 2.3.4.4b. The first group includes 2016-2017 Nigerian viruses with high genetic similarity to H5N8 viruses detected in Central African countries, while the second includes Nigerian viruses collected both in LBM and poultry farms (2018-2019), as well as in Cameroon, Egypt and Siberia. A natural reassortant strain, identified in 2019 represents the third group: H5N8 viruses with the same gene constellation were identified in 2018 in South Africa. Finally, the fourth introduction represents the first detection in the African continent of the H5N6 subtype, which is related to European viruses. Bayesian phylogeographic analyses confirmed that the four introductions originated from different sources and provide evidence of the virus spread within Nigeria, as well as diffusion beyond its borders. The multiple epidemiological links between Nigeria, Central and Southern African countries highlight the need for harmonized and coordinated surveillance system to control AIV impact. Improved surveillance at the Wetlands, LBMs and early warning of outbreaks are crucial for prevention and control of AIV, which can be potentially zoonotic and be a threat to human health.