Легенда соединяет Немею с первым из двенадцати подвигов величайшего греческого героя Геракла. Именно здесь, как гласят мифы, Геркулес победил Немейского льва, а после победы оделся в его шкуру, которая с той поры стала постоянным атрибутом героя. Грот, в котором будто бы находился лев, был недалеко от стадиона, построенного несколько веков спустя.
Предположение о том, что Немейские игры были учреждены Гераклом в честь его победы над Немейским львом и в благодарность своему отцу Зевсу, следует считать неверным. В древних источниках до I в. н.э. Немейские игры никак не связывались с Гераклом. Среди археологических находок, которые можно было бы отнести к Гераклу, имеется только рельеф на золотой фольге с лицом Геракла со львиной шкурой, завязанной под подбородком. Но этот артефакт недостаточен для того, чтобы как-то соотносить Немейские игры и Геракла.
Мифология Немейских игр была отражена в несохранившейся трагедии Эсихла, а также в трагедии Еврипида "Гипсипила" и, возможно, на одном из египетских папирусов. Эта мифология связана с историей гибели младенца Офельта – сына царя (или жреца) Ликурга и Эвридики. Оракул сообщил Ликургу, что его сын не должен касаться земли, пока не научится ходить. Ухаживала за младенцем Гипсипила, относительно которой имеется собственное предание – будто бы она была лемносской царицей и сошлась с Ясоном во время стоянки аргонавтов у ее острова. И потом была продана в рабство то ли своими согражданами, то ли захватившими ее пиратами. Так вот, именно рабыне Гипсипиле было поручено заботиться о соблюдении условия: Офельт не должен касаться земли. Но когда Гипсипила встретила войско пелопоннесских владык, следовавших на завоевание Фив, она вынуждена была показать им источник питьевой воды, где и положила ребенка на подстилку из дикого сельдерея, чтобы наполнить сосуд и напоить царей и героев.
Когда рабыня отвернулась, змея убила ребенка, и участники похода "Семеро против Фив" расценили это как дурное предзнаменование. Прозвав ребенка Архемором ("властителем рока"), они провели погребальные игры в попытке умилостивить богов. Это и были первые Немейские игры. Их участники были облачены в темные траурные одежды, а победителю вручался венок из дикого сельдерея. Одно из немногих изображений, связанных с этим мифом, размещено на римском саркофаге, представленным в Коринфском музее.
Поза бронзовой фигурки младенца (эллинистический период), найденной к югу от Храма Зевса, сходна с позой Офельта на коринфском саркофаге. Но ее достоверность невелика, поскольку данная находка обнаружилась в слоях, относящихся к VI в. н.э.
Мифология Немеи восходит к событиям 13 в. до н.э., вслед за которыми последовало уничтожение Фив, Троянская война и крах Микенской цивилизации.
С левой стороны холма Тсунгиза археологами была обнаружена группа доисторических артефактов. Некоторые из них происходят из области святилища Зевса, но большинство – из Тсунгизы. Находки включают в себя множество инструментов – таких как каменные зернотерки, каменные топоры, обсидиановые лезвия. От периода поздней бронзы (микенский период) сохранилось навершие меча, группа терракотовых фигурок и бронзовый кинжал с костяной ручкой.
С правой стороны холма имеются слабые зачатки деятельности после "темных веков" (1100-700 гг. до н. э.) – это упадок, коснувшийся всей Микенской цивилизации. Лишь с 8 в. до н. э. начинается возрождение. Фрагменты керамики этого периода были найдены недалеко от храма и алтаря Зевса. На них имеются характерные геометрические орнаменты. Из этого же периода – маленький бронзовый конь, обнаруженный при раскопках холма, граничащего со стадионом более поздней эпохи. Но процветание Немеи началось только в 6 в. до н.э. с проведением здесь общеэллинских игр – вместе с увеличением посещения святилища Зевса.
Немея выполняла роль святилища, находилась вблизи путей, соединявших северный и южных Пелопоннес – прежде всего Аргос и Коринф. Поэтому Немея не раз подвергалась разрушениям в результате конкуренции могущественных государств Пелопоннеса, борющихся за право проводить игры. Также известна битва, происшедшая в 394 г. до н. э. близ Немеи, когда Спарта и ее союзники (Ахайя, Элида, Мантинея и Тегея) разбили Афинскую коалицию (Афины, Беотия, Эвбея, Коринф и Аргос). Спартанцы на своем фланге атаковали афинский контингент и разбили его, пожертвовав ради победы левым флангом, где их союзники понесли большие потери.