Grajewo nad Ełkiem powstało w XV wieku z inicjatywy księcia mazowieckiego, Janusza I. Nazwa miasta pochodzi od nieistniejącego już jeziora Krejwy.
W 1426 r. książę Janusz po raz pierwszy wymienił nazwę książęcej wsi Graywa. Wzmiankę odnaleźć można w metryce książąt mazowieckich. W 1434 r. Bolesław IV (wnuk Janusza I) nadał Włościborowi z Osieka 60 włók, zwanych Graywo.

Jan z Białowieży (nadworny księcia Kazimierza III i starosta biskupich dóbr pułtuskich) otrzymał 23.XI.1472 roku ziemie wraz z Grajewem. W 1478 roku ufundowano we wsi został kościół Świętej Trójcy, a w roku 14 VII 1479 Kazimierz Mazowiecki stworzył tu parafię. Od roku 1483 Jan z Białowieży przyjął nazwisko - Grajewski.

Wzrost liczby mieszkańców wsi pozwolił na rozwój handlu i rzemiosła. Rzeką Ełk, przepływającą obok Grajewa, szlachta pruska spławiała zboże i towary leśne do Gdańska. Wioska była dla nich ostatnim postojem przed wpłynięciem na tereny niezamieszkałe. Grajewo posiadało królewskie pozwolenie z 1567 r. na wyrób smoły, popiołów i innych towarów leśnych w lasach królewskich oraz na ich eksport do Gdańska.

Grajewo prawa miejskie otrzymało 12 VII 1540 r.
Mimo korzystnego położenia geograficznego miasto nie rozwijało się. Rozwój hamował między innymi niewygodny podział miasta między wielu spadkobierców.

Dopiero kiedy w XVII w. miasto w całości wykupił najbogatszy z rodu w rejestrach Grajewo zaczęło być zapisywane jako miasto.
Grajewo było właściwie wsią targową. W 1692 miasto przeszło w posiadanie Wilczewskich dzięki małżeństwu córki Jakuba Grajewskiego, Anny. Pod koniec XVII w. Grajewo zaczęło się rozwijać. Zabudowa ograniczała się do rynku i ulic wylotowych. W 1818 otwarto w mieście fabrykę świec oraz mydła. Rocznie odbywały się cztery jarmarki. Handlowano głównie bydłem, końmi i wyrobami bednarskimi. Około 1850 liczba ludności wzrosła do około 1917 osób. W 1800 roku miasto liczyło tylko ok. 200 mieszkańców. Miejscowość posiadała stację pocztową, komorę celną, szkołę elementarną, rzeźnię, a także wiele zakładów rzemieślniczych. W 1870 roku, z powodu udziału mieszkańców Grajewa w powstaniu styczniowym, odebrano miastu prawa. 

Rozkwit Grajewa nastąpił po wybudowaniu szosy petersburskiej oraz kolei żelaznej Brześć - Królewiec w 1873 roku. W Grajewie powstała stacja przeładunkowa. W efekcie zmieniła się także zabudowa miasta. Domy budowano wzdłuż trakcji kolejowej. Powstało także kilka zakładów przemysłowych: fabryka win, gorzelnia, huta szkła, fabryka pasów transmisyjnych i taśm gumowych, betoniarnia.

W 1894 roku w Grajewie wybudowano koszary a do miasta przybyli rosyjscy wojskowi wraz z rodzinami. Powstała dla nich niewielka cerkiew wraz z cmentarzem.

Podczas I wojny światowej miasto zostało zniszczone przez armię niemiecką.
W okresie międzywojennym Grajewo było siedzibą starostwa szczuczyńskiego i liczyło około 9500 mieszkańców. Bliskość granicy z Prusami Wschodnimi korzystnie wpływała na rozwój życia gospodarczego. W 1922 r. Grajewo ponownie otrzymało prawa miejskie. W okresie międzywojennym było ośrodkiem o charakterze administracyjno-usługowym. W mieście stacjonował 9. Pułk Strzelców Konnych im. gen. K. Pułaskiego.

Na przełomie sierpnia i września 1941 r. utworzono w mieście getto, w którym przebywało około 4,5 tys. osób. We wrześniu 1942 podjęta została decyzja o likwidacji getta. 15 lipca 1943 gestapo zamordowało w Grajewie 183 osoby, głównie lokalną inteligencję, w pobliskich Boguszach.

20 stycznia 1945 r., w przeddzień opuszczenia Grajewa, Niemcy wymordowali znaczną część miejscowej ludności w lesie Kosówka.