Winter cover crops are beneficial, especially legumes that can supply nitrogen (N) to the next crop. The purpose of this study, involving separate experiments carried out at 2 different locations in north-eastern Slovenia, was to determine the most appropriate sowing time (early, early autumn SD1; late, mid autumn SD2; very late, late autumn SD3) for winter legumes (Trifolium subterraneum L., T. incarnatum L., T. pratense L., and Vicia villosa Roth) for the optimal yield of beneficial dry matter and soil N cycling. The control treatment used Lolium multiflorum Lam. For legume cover crops in SD1, from 915.0 (T. subterraneum) to 2495.0 (V. villosa) kg herbage dry matter yield (HDMY)/ha, 52.3 (T. pratense) to 148.4 (T. incarnatum) kg accumulated N (AN)/ha, and 14.5 (T. pratense) to 114.5 (T. incarnatum) kg symbiotically fixed N (N_symb)/ha was obtained to the end of autumn. Until the spring ploughing-in, which was before maize sowing, legume cover crops in SD1 yielded 1065.0 (T. subterraneum) to 4440.0 (T. incarnatum) kg HDMY/ha, 74.9 (T. subterraneum) to 193.0 (V. villosa) kg AN/ha, and 4.7 (T. subterraneum) to 179.0 (V. villosa) kg N_symb/ha. All parameters in SD2 were significantly lower than in SD1, whereas the SD3 sowing was not suitable for the legumes. The benefits of legume winter cover crops with regard to symbiotic N fixation were achieved only by early sowing; however, the amount of soil mineral N in late autumn and in early spring was decreased under L. multiflorum more than under the legumes.