Millonarios, razem z drużynami Atlético Nacional z Medellin i America z Cali, było powiązane z kolumbijskim handlarzem narkotyków Gonzalo Rodriguezem Gachasem. Dzięki jego wsparciu finansowemu klub sięgnął po dwa tytuły mistrza Kolumbii: w 1987 i 1988.
W Millonarios grało wielu słynnych piłkarzy, jak Atilio Ancheta, Juan Gilberto Funes, „El Búfalo”, Willington Ortiz, Arnoldo Iguarán, Daniel „Tito” Onega, Fernando Areán, Carlos Valderrama, Carlos Ángel López, Alfredo Castillo, Sergio Goycochea, Delio „Maravilla” Gamboa, Miguel Angel Converti, Jaime Morón, Amadeo Carrizo, Alejandro Brand, Pedro Alberto Vivalda, Arnoldo Iguarán i inni.
Począwszy od roku 2000 klub znalazł się w trudnej sytuacji finansowej z powodu śmierci Jose Gonzalo Rodrigueza Gachasa (handlarz narkotykowy zabity przez kolumbijską policję), co spowodowało słabsze występy w lidze.
Obecnie klub jest w trakcie procesu o bankructwo, który ma oczyścić go z długów i pozwolić rozpocząć nowy rozdział w kolumbijskim futbolu.
Z powodu finansowych problemów klub Millonarios musiał w 2005 roku zrezygnować z planów budowy własnego stadionu na obrzeżach Bogoty.