Niewino Kamieńskie było częścią okolicy szlacheckiej Niewino powstałej jeszcze w XVI wieku. Ta miejscowość leżała w centrum tej okolicy szlacheckiej i tu właśnie najwięcej było zmian osadniczych. Pierwsze dane o wsi pochodzą z 1528 roku, zwała się ówcześnie Kamenka i liczyła zaledwie 1 rycerza Mateya Michayłowicza. Obok istniała wioska o nazwie Niwino Jeżowskii, zamieszkała przez dwóch rycerzy Mikołaja Jeżewicza i zapewne jego brata Martina Jeżewicza. Właśnie to najlepiej pokazuje w jaki sposób powstawały osiedla drobnoszlacheckie tworzące okolice szlachecką. Bracia Jeżewicze byli zapewne synami rycerza zwanego Jeżewiczem, który tu zamieszkał w końcu XV wieku. Natomiast Matey Michayłowicz był synem Michała, który zamieszkał tu w tym samym czasie. Zarówno Michał jak i Jeż poprzez odłączenie się od rodowej wsi (zapewne Niewino Stare lub Popławy) doprowadzili do utworzenie nowych wiosek, mimo że tak niewielkich liczących początkowo po 1 -2 domy. Obecnie takie osiedla były by przyłączone do którejś z sąsiednich wsi, lecz wtedy stanowiły osobne osiedla umieszczany w ówczesnych spisach. Mieszkali tu ubodzy rycerze, w sumie mogli wystawić 1 rycerza na potrzeby wojenne.
Takie niewielkie osiedla często zanikały lub też były wchłonięte przez sąsiednie wsie, powstawały za to nowe. Tak się stało z Niewinem Janowiata, które notowano jest w początkach XVI wieku i potem nie o nim śladu. Za to pojawiają się osady Spaszy i Mruczki (rok 1580), które potem również zaniknęły. Również Niewino Jeżowskich zaniknęło, zostało zapewne wchłonięte przez sąsiednie Niewino Kamieńskie, które i tak było niewielkim osiedlem, gdyż w 1580 roku wymieniano go razem z Niewinem Leśnym.
Przez kolejne stulecia była to maleńka wioska drobnoszlachecka. Na mapach z końca XVIII wieku pojawia się nazwa Kamieńskie Rytolewszczyzny, której nie używano później ani wcześniej.
Słownik Geograficzny wspomina tę miejscowość obok innych Niewin. W 1921 roku notowano tutaj zaledwie 8 domów i 42 mieszkańców, w tym 1 prawosławnego. Miejscowość należała do gminy Wyszki.
