Rylsk vart første gong nemnd i skriftlege kjelder i 1152 som ein av dei severiske byane. Han vart eit senter for eit apanasje-fyrstedøme på slutten av 1100-talet før han hamna under Storhertugdømet Litauen sine herskarar ein gong på 1300-talet. Kasimir IV gav han til sonen til Dmitrij Sjemjaka, Ivan, som hadde busett seg i Litauen. Son til Ivan, Vasilij, hoppa over til Storfyrstedømet Moskva, men litauarane heldt byen til 1522. Under urotida i Russland var han ein av dei første byane som ønskte den falske Dmitrij velkommen som tsar. Etter Ukraina vart innlemma i det russiske keisardømet drog Rylsk fordelar av handelen mellom Ukraina og det øvrige Russland og det budde mange handelsmenn i byen.