Deras flyg från Slovenien till Storbritannien avleds till Köln efter att piloten larmades om ett "misstänkt samtal" med "terroristinnehåll".
"Den brottsutredningen mot dem har stoppats. Inga bevis hittades, sa polisen.
"Vi tror nu att det aldrig fanns någon verklig fara."
Alla 151 passagerare evakuerades från Airbus 319 flygplan med hjälp av nödrutschbanor, och nio fick medicinsk behandling.
Männen, 31, 38 och 48 år, återvände till Stansted, i Essex, från Ljubljana den 10 juni när störningen uppstod. De sägs ha varit på affärsresa.
Enligt åklagare avleds flygningen när medpassagerare rapporterade att männen diskuterade "terroristfrågor" och bar en bok med titeln "Död" med ett krypskyttegevär på omslaget.
De sade att innehållet i den påstådda konversationen inte kunde verifieras.
Inga sprängämnen hittades i passagerarnas bagage eller på planet. En ryggsäck som tillhörde männen sprängdes ändå av polisen.
Den tyska tabloidtidningen Bild sade att passagerarna sade till flygpersonalen att de hade hört männen använda orden "bomba" och "explosiva", och sade att man bar på en misstänkt ryggsäck.
En talesman för flygplatsen Köln-Bonn sade: " Piloten hade informerats om ett misstänkt samtal ombord, varefter han bestämde sig för att göra en oplanerad landning i Köln-Bonn.
"Efter den säkra landningen lämnade de 151 passagerarna [flyget] via nödrutschbanor och fördes till en transitport."
Planet landade på Stansted-flygplatsen på söndag.
Passageraren Daniel Noonan berättade för BBC att beväpnade poliser kom in i flygplanet och eskorterade två män av. Den tredje leddes bort på asfalten efter att passagerarna hade gått ut via rutschkanorna.
Passageraren Richard Peters sa att han såg de två asiatiska männen bli handfängslade på flygplatsen i Köln-Bonn.
Han tillade att människor på flygningen satt i karantän i omkring nio timmar medan polisen intervjuade passagerarna om männen.
Han sade: " Att vara rättviseand var ganska högt med tanke på vad som hade hänt.
"I det nuvarande klimatet måste man ta allt på allvar. Min misstanke är att det förhoppningsvis inte var något illvilligt. Men du måste ta allt på allvar.
"Det rätta var gjort."
En annan passagerare, Dave Hargreaves, sade: " Under flygningen såg jag inte de misstänkta alls. Men jag lade märke till en hel del aktivitet, med luftskruvar som dyker upp i cockpit upprepade gånger. Och en långsammare än normalt servering av mat och dryck.
"Då på vår marschhöjd blev jag förvånad över att se luftbromsarna gå upp på vingarna och vi börjar en ganska snabb nedstigning. Det var kanske inte förrän tio minuter senare som vi fick höra "av operativa skäl" att vi skulle avleda till flygplatsen i Köln."
Easyjet sa att kaptenen hade fattat beslutet att landa som en försiktighetsåtgärd för att tillåta ytterligare säkerhetskontroller.
Alla de andra passagerarna fick ett hotell för natten, sade en taleskvinna och tillade: " Vi tackar passagerarna för deras förståelse. Säkerheten hos Easyjets passagerare och besättning är vår högsta prioritet."
Få nyheter från BBC i din inkorg, varje vardag morgon
Tre brittiska män som fängslades i Tyskland efter sina samtal ombord på en Easyjet-flygning utlöste larm har släppts utan kostnad.