Un cimetière des VIe-VIIIe siècle, composé de tombes en molasse typique atteste de l'occupation humaine durant le haut Moyen Âge.
Le lieu dit la Cour, à l'est du chef-lieu fait référence à la résidence d'un aristocrate à l'époque mérovingienne et/ou carolingienne.
À partir de l'an mil, les habitants et les terres sont soumis à divers seigneurs : les nobles de Pontverre, les seigneurs de la Croix etc.
Son territoire relève alors de la châtellenie de Cruseilles qui appartenaient aux comtes de Genève. Mais les principaux seigneurs sont les nobles de Menthonay qui détiennent les seigneuries de Villy et Menthonnex et celle du Turchet, dont le cœur est une maison forte située au nord-est du chef lieu qui commandait un chemin de desserte et les moulins en contrebas.
D'abord paroisse indépendante, Menthonnex devient une filiale de celle de Villy-le-Bouveret, sans doute après la terrible épidémie de peste noire qui a dû décimer presque la moitié de la population. Les curés du lieu doivent composer avec le puissant chapitre de Saint-Pierre de Genève qui possède des biens et des droits sur le territoire de Menthonnex. À la fin du Moyen Âge, l'église est dans un état lamentable, le chœur s'effondrant. Elle est rénovée et consacrée en 1486.
Les premières évaluations écrites sur la population donnent environ 135 habitants vers 1443. Par la suite, la population augment progressivement pour atteindre un maximum de 422 habitants vers le milieu du XVIe siècle.