Początki miejscowości (Zobacz Majdany Wielkie na mapie Współrzędne: 53° 47' 34.14'' N 19° 46' 51.65'' E; 53.792818, 19.781013) datują się na aktywność zakonu krzyżackiego w tym regionie w początkach XIV wieku. Zanim Luter z Brunszwiku, przyszły wielki mistrz zakonu krzyżackiego nadał prawa miejskie Ostródzie, osadził w Majdanach nowych dzierżawców. Dnia 4 grudnia 1322 roku nadał im na prawie chełmińskim siedemdzisiąt łanów ziemi, kościołowi jak to często w owym czasie bywało, przypadły z tego całe cztery łany. Mieszkańcy mieli za zadanie wybudować kościół lub kaplicę. Budowla ta niestety nie przetrwała do czasów współczesnych, pozostał po niej jedynie ślad na XVIII wiecznych mapach. Osada nazywała się wtedy Aldenhayn i podlegała pod dzieżgońską kamerę komturską w Karpowie. Po wojnie 1410 roku "kiedy Miłomłyn zdobyli Polacy", trzynaście wsi w tym Majdany przeszły pod zwierzchnictwo Miłomłyna.
Ta licząca przed II wojną światową prawie 500 mieszkańców wioska, połączona była ze światem żelazną drogą. Wybudowana w latach 1891-1893 linia kolejowa do 1945 roku łączyła Majdany z Elblągiem i Ostródą.
Obok dawnego cmentarza w 2017 r. wybudowano piękną przydrożną kapliczkę.