The tumultuous trajectories of COVID-19 undoubtedly reached all national structures and functions, and their international equivalents. This paper examines the nexus between the global onslaught of the enraging pathogens and the leadership challenges still embedded in Nigeria’s federalism. The general objective of the paper therefore was to study the COVID-19 pandemic, federalism and Nigeria’s leadership challenges. The paper is anchored on structural functionalism as theoretical framework, under a qualitative and normative methodological design. The work prognosticates that after COVID-19, the deadly viruses are coming again and advises that when they come back, structurally and functionally, they must not meet Nigeria the way the novel coronavirus found it. The paper recommends the development of an inexhaustible pool of leaders in the country by converting the current senatorial zones (with the exclusion of Abuja where the Federal Capital Territory Minister performs functions of similitude with that of a State Governor) into Nigeria’s new federating states, and the current state demarcations converted into 37 senatorial zones. This translates to 108 states in the country.