In the midst of Would War-II, Hitler realized he needed an extra edge to help him win the war, and thus he started poring over his own interest in the supernatural. During these times, the infamous Order 666 was issued by the Chancellery to have a special division to research supernatural creatures and the replication of their powers, in order to strengthen the failing Nazi soldiers. The responsibility of this Projekt fell upon a SS officer simply addressed as the Major, his adjutant and bodyguard, the Captain, and a specialist in the supernatural and a depraved geneticist, physicist, robotic engineer and genius, named Avondale Napyeer (usually addressed as the Doctor or Doc).
A camp in Warsaw was entrusted to this purpose, and there, the Doctor experimented upon tissue and fluids recovered from a mummified, bandaged and chained corpse, much later revealed to be the decomposing cadaver of Mina Harker, still struggling through undeath due to Alucard's impure blood (which was never remover, nor the curse lifted, due to Alucard's enslavement to Hellsing). The horrors of the camp were so terrible they could not be hidden for long, and soon enough Hellsing operatives Walter C. Donez and Alucard infiltrated and destroyed the camp through still unknown circumstances. Unusually for the massive destruction they wrought, most of the top men in charge of the Order were left as survivors, eventually teaming up with the Vatican to move out their weapons, their war loot and their research overseas to South America, where they regrouped as the Millennium Group.
After decades, the vampire conversion surgery protocols were prepared and refined, and soon enough the Letzte Bataillon, a detachment of a thousand vampires, was ready to be moved out and properly tested. The highest authority in the Bataillon, save for the Major himself, came either from the Doctor or from the elite Werwolf squad, composed by successful experiments whose power marked them as far above normal vampires. Members of the Werwolf squad were: the Captain as the leader, Schrodinger and Luke Valentine as Warrant Officers, and Zorin Blitz, Rip Van Winkle and Tubalcain Alhambra as First Lieutenants. To preserve the Major, he was eventually transferred to a cyborg body; the Doctor's own augmentations remain unknown.
Millennium started then mass-producing vampires and pouring them through England, to probe the waters and accurately assess the Hellsing organization's capability in handling these threats. Satisfied by the results, the Major had a group led by the Valentine Brothers attack Hellsing HQ with an army of ghouls; the mission ended up a failure, despite annihilating Hellsing forces except for the two survivors and the two undead that shrugged off the attack: Integra Hellsing and Walter C. Dornez for the first, and Seras Victoria and Alucard for the latter. Later on, before the next phase of his plan was implemented, the Major almost had control over the group wrestled from him by a band of elderly Nazi generals of higher ranking, who craved immortality. Perceiving these men as defeatists, the Major simply had them executed.
He then had Rip Van Winkle take control over the British VTOL carrier the Eagle, and serve as a bait to lure Alucard to deep waters and strand him there, as he could not cross the ocean without an external means of locomotion. However, he retook control of the ship by sheer willpower an started moving it with black sails toward England. As Alucard was blocked from interfering, the Major had the Millennium Army deployed with a missile salvo upon London. Spectacularly levelling the city, he had the entire army deployed to cause maximum damage until the organization experienced its first losses when fighting against the Iscariot Organization envoys, losing potential prisoner Integra Hellsing in the process.
Still worse was when elite operative Zorin Blitz ignored orders issued by the Major and had the zeppelin and batallion under her command to assault Hellsing HQ before reinforcements were readily available, supposing the humans within would be ill-equipped to fight against Millennium's vampires. This tactical move cost her dearly as the fledging Seras Victoria used a massive weapons system to destroy the zeppelin and its missile cargo and the vampires on ground were hit by the mine network hidden under the manor's lawn by the resident defenders and the specialized weapons the mercenaries wielded; she, however, minimized these effects by ordering the evacuation of the zeppelin and using her illusory abilities to create a mirage of herself grown to a gigantic size and hacking at the manor. This allowed for infiltration and made an abattoir of the mansion. Zorin, however, chose to cripple Victoria rather than outright killing her, another move that came back to haunt her as the fledging chose that moment to embrace her vampirism fully and activated her latent powers, all but shredding the enemy team and brutally executing Zorin, effectively winning the battle for Hellsing.
Then a worse setback came in the form of the full might of the Vatican's army, led by Archepiscopus Enrico Maxwell, head of Section XIII. Banding apparently benign, independent organizations such as the Knights of the Order of Malta, the Knights of the Sagely Brethren, the Knights of the Order of Calatrava la Nueva, and the Knights of the Military Order of Saint Stefano di Toscana, Iscariot had them armed and geared them up to serve as a new Crusade's armies, forming an army of over three thousand human men to go against Millennium's thousand vampires. However, Vatican efforts were hindered by Maxwell's Christian fanaticism, leading him to order the deaths of all London protestants rather than focusing on the extermination of the Letzte Bataillon.
Finally, a grand battle erupted between the Iscariot forces, still over twenty-seven hundred men, the Millennium army, slightly above five hundreds, and Alucard's familiars, representing the Army of Hellsing, numbering on the millions. Upon the confrontation, the Batallion was all but annihilated in the crossfire. The remnants of the Batallion were destroyed after the Major's last cards, the vampirized Walter and the Captain, were slain. While triumphant in their goal to temporarily banish Alucard, Millennium ultimately proved to be a fool's dream, as no survivors of the team were recorded to survive the England assault, and instead awakened a vampire that could prove to be Alucard's match: the Draculina Seras Victoria, cemented Integra Hellsing's faith in humanity, and ultimately endowed Alucard with all of Schrodinger's abilities.