Přestože BepiColombo odstartoval teprve před týdnem a do své destinace doputuje až na konci roku 2025, první návrh evropské mise k Merkuru byl předložen už v květnu roku 1993 v rámci programu Horizons 2000. Prvotní odhady však prokázaly, že realizace v rámci kategorie středně velkých misí by byla až příliš nákladná. Mezi tyto středně velké projekty patří například přistávací modulu Hyugens nebo mikrovlnný teleskop Planck. Na navrhovanou misi k Merkuru se však usmálo štěstí. Program Horizons 2000 byl v roce 1994 prodloužen (nyní nesoucí označení Horizons 2000+) a díky tomu měly být vybrány další tzv. „cornerstone“ mise neboli základní kameny výzkumu či vlajkové lodě. Ty jsou definovány jako nejnákladnější projekty světové úrovně s vysokým vědeckým potenciálem, vyžadující ke svému uskutečnění významný pokrok v technologickém vývoji. První misí v kategorii cornerstone byla doposud fungující veleúspěšná sluneční observatoř SOHO. Dále bychom zde mohli zařadit rentgenový teleskop XMM-Newton, infračervený teleskop Herschel nebo kometární průzkumné duo Rosetta-Philae – všechno nesmírně úspěšné a přínosné mise, které nemalou měrou posunuly míru lidského poznání. Návrh BepiColombo usiloval zařadit se mezi tyto giganty a jeho soupeřem se stala rovněž velmi ambiciózní astrometrická družice Gaia. V říjnu 2000 pak k velkému uspokojení všech byly oba návrhy vybrány pro realizaci mezi lety 2008 – 2013. Práce na evropské misi k Merkuru tak mohly začít.