A first alternating stack of first insulating layers and first sacrificial material layers is formed with a first stepped surfaces located in a staircase region. A second alternating stack of second insulating layers and second sacrificial material layers with second stepped surfaces is formed over the first alternating stack. Areas of the second stepped surfaces overlap areas of the first stepped surfaces to reduce the size of the staircase region. The sacrificial material layers are subsequently replaced with electrically conductive layers. Laterally-insulated staircase region via structures contacting a respective one of the electrically conductive layers may be provided by forming stepped via cavities such that an annular surface of a respective sacrificial material layer is physically exposed at an annular step of the stepped via cavities. Laterally-insulated staircase region via structures may be formed in the stepped via cavities tot provide electrical connections to the electrically conductive layers.