We treat theoretically the initial nucleation step of self-catalyzed III-V nanowires under simultaneously deposited group III and V vapor fluxes and with surface diffusion of a group III element. Our model is capable of describing the droplet size at which the very first nanowire monolayer nucleates depending on the element fluxes and surface temperature. This size determines the initial nanowire radius in growth techniques without pre-deposition of gallium. We show that useful self-catalyzed III-V nanowires can form only under the appropriately balanced V/III flux ratios and temperatures. Such balance is required to obtain nucleation from reasonably sized droplets that are neither too small under excessive arsenic flux nor too large in the arsenic-poor conditions.