Takım Himki kentinin iki amatör takımı olan Rodina ve Novator'un birleştirilmesiyle oluştu. Himki amatör lige katıldı ve ilk resmi karşılaşmasını 17 Mayıs 1996'da oynadı. 150'den fazla takımın katılıp sadece şampiyonların üçüncü lige kalabildiği turnuvada Himki Energiya Ulyanovsk'a karşı penaltı vuruşları sonunda kazandı.
30 Ocak 1997'de Himki artık profesyonel bir takım oldu. Üçüncü lig bölgesel turnuvalarında ikinci olarak 2. Lige yükselmeye hak kazandı.
Himki, 2000 sezonundan sonra 1. Lige yükselmeyi başardı. 2. Lig'in merkez bölümünü birincilikle bitirdi fakat play-off karşılaşmasını deplasmanda yediği gollerle Severstal Cherepovets'e kaybetti. Severstal 1. Lig'de oynamayı geri çevirince FK Himki 1. Lig'de oynamaya hak kazandı.
2005 yılında Himki Kubok Rossii'de güzel bir seri yakalayarak finale kadar ulaştı fakat final karşılaşmasında CSKA'ya 1-0 'lık sonuçla yenildi.
