OLECKO MAŁE już istniało w 1541 roku, gdyż książę Albrecht podał do wiadomości w roku następnym, że Bartosz Leśnicki z Mazowsza kupił od starosty książęcego w Stradunach osiem włók sołeckich na prawie chełmińskim w celu wykarczowania boru i założenia wsi na 60 włókach między Kleszczewem a Wieliczkami. Do włók sołeckich należała też wyspa. Zachował się przywilej lokacyjny tej miejscowości z 11 lutego 1542 roku. Szkoła powstała tu pomiędzy rokiem 1763 a 1786. Aż do XX wieku wieś miała podwójną nazwę: Olecko Małe i Pierdzilewo (lub Pierdziłowo), które wywodziło się od przezwiska - znanego na Mazurach sposobu tworzenia nazw miejscowych (np.Bździele, pow.ełcki). W 1938 roku Olecko Małe liczyło 518 mieszkańców. Nazwę wsi ustalono w tym roku na Herzogshöhe. Starosty STAROSTY powstały w wyniku podwójnego nadania. Najpierw książę Albrecht nadał Mikołajowi z Kleszczewa - "staroście" (stąd nazwa wsi) sześć i ćwierć włóki oraz dwie dalsze podarował za zasługi. Rzecz miała miejsce 8 stycznia 1538 roku. W roku 1563 tenże książę Albrecht nadał Mikołajowi Müllerowi z Kleszczewa dwie włóki z młynem. Około 1800 roku była to wieś szlachecka, z młynem wodnym i jednoklasową szkołą, która powstała jednak później i uległa z czasem likwidacji. W 1938 roku Starosty liczyły 84 mieszkańców i nosiły nazwę niemiecką Müllersbruck.