Założony w Step-Soci, po przenosinach do Orhei sięgnął po mistrzostwo Mołdawii w 2015 i 2025 roku.
Domem zespołu jest Complexul Sportiv Raional Orhei. Stadion otwarto w 1980 roku, a przebudowany obiekt oddano do użytku 22 maja 2007. Modernizacja objęła zastąpienie drewnianej trybuny nową konstrukcją i powstanie bieżni.
Klubowe kolory to biel i czerwień.
Klub powstał w 2005 roku jako Viitorul Step-Soci. Pierwszy oficjalny mecz rozegrał 21 sierpnia tego roku w Divizia B Nord, remisując na wyjeździe z FC Florești 0:0. W sezonie 2008/09 przeniósł się do Orhei, a w 2010 przyjął nazwę Milsami. Rok później połączył się z FC Ursidos Chișinău i występował jako Milsami-Ursidos.
Pierwszy Puchar Mołdawii zdobył w maju 2012. Finał z CSCA-Rapid zakończył się bezbramkowo po dogrywce, a decydujący rzut karny w wygranej 5:3 serii wykorzystał kapitan Andrian Sosnovschi. W tym samym roku Milsami pokonało Sheriffa w superpucharze, również po remisie 0:0 i jedenastkach. Bohaterem został Adrian Negai: bronił groźne strzały podczas meczu, a na koniec zatrzymał karny Darwina Riosa.
Pierwsze mistrzostwo przyszło w sezonie 2014/15. Zespół Iuriego Osipenco w ostatniej kolejce wygrał na wyjeździe z Dacią Chișinău 2:1. Milsami, Dacia i Sheriff zakończyły rozgrywki z taką samą liczbą punktów, a o tytule zdecydował bilans bezpośrednich spotkań. Latem Milsami wyeliminowało Łudogorca Razgrad w kwalifikacjach Ligi Mistrzów, wygrywając oba mecze: 1:0 i 2:1. Gola w Bułgarii strzelił Alexandru Antoniuc.
Drugi puchar zdobyło 23 maja 2018. Rezerwowy Maxim Antoniuc strzelił obie bramki w dogrywce finału z Zimbru Chișinău, wygranego 2:0.
18 maja 2025 Milsami ponownie zostało mistrzem Mołdawii. Tytuł zapewnił mu remis 0:0 na stadionie Sheriffa w Tyraspolu.
