En 2020, les Ulinzi Starlets terminent leur saison invaincues en deuxième division et sont promues en KWPL. Lors de leur première saison dans l'élite, elles atteignent les play-offs et sont éliminée aux tirs au but par les Nakuru City Queens[3].
Les Ulinzi Starlets décrochent leur premier titre en 2021 en remportant la coupe du Kenya face aux Vihiga Queens, tout juste championnes du CECAFA (2-1). Elles remportent la supercoupe aux tirs au but face aux Thika Queens (1-1, 10-9)[4]. Elles défendent leur titre en 2023 et dominent Nakuru 3-1 en finale pour réaliser le doublé[5]. Les Soldates battent ensuite Vihiga 2-0 en supercoupe[6].
En 2024, Ulinzi soulève son troisième trophée en coupe du Kenya en trois éditions, après avoir battu Kibera 2-1 en finale[7].