No início do século XIX, a expanSão da cultura cafeeira no Vale do Paraíba propiciou o aparecimento de diversos núcleos espontâneos de povoamento, entre os quais, Santa Cruz do Paiolinho, atual Redenção da Serra.

Iniciou-se quando o capitão-mor, Francisco Ferraz de Araújo, juntamente com sua mulher, Dona Francisca Galvão de França e numerosos escravos, cumprindo à ordem do Governador da Província, penetrou o sertão das Samambaias e ao encontrar o Rio Paraitinga, ali fixou residência e iniciou roças de milho e outros produtos agrícolas. Segundo diz a tradição, um de seus escravos faleceu ao construir o caminho que ia até sua casa, a uns 9 km. Neste local foi erguida uma cruz de madeira. Ao seu redor foi surgindo um povoado sendo o mesmo favorecido pelo capitão-mor, pois quando as pessoas iam até ele pedindo terras para cultivo, ele as cedia próximas à cruz. Logo surgiu ali uma capela. Este povoado recebeu o nome de Paiolinho devido ao fato de um dos moradores ter feito sua roça de linho e, depois das fibras secas, elas eram postas em um paiol (paiol-e-linho). O vigário Pe. José Grecco juntamente com uma comisSão de obras levantou nesta época sua Igreja Matriz.

O lugar, graças à cultura cafeeira, cresceu e foi elevado à categoria de Paz segundo a Lei Provincial nº 3, de 24 de março de 1860. Suas divisas com Taubaté foram demarcadas a 23 de março de 1861. Com isso, Paiolinho progrediu mais acentuadamente. Os fazendeiros de café ergueram sobrados majestosos com longos beirais, janelas com arcadas e também casas térreas com uma arquitetura marcante.

A População cresceu e a produção agrícola apresentava boas safras, o que levou Paiolinho a ser elevada à categoria de município segundo Lei Provincial nº 33, de 8 de maio de 1877. O município possuía sede na povoação de paiolinho e seus territórios foram desmembrados do município de Taubaté, tendo sua instalação a 1º de dezembro do mesmo ano. Voltou à condição de distrito pela Lei nº 6448 de 21 de maio de 1934 quando foi incorporado ao município pelo Decreto nº 7353 de 5 de julho de 1935 e a pertencer a comarca de Taubaté, sendo reinstalado a 1º de janeiro de 1936.

A necessidade ficar o quadro administrativo, territorial e judiciário do Estado de São Paulo, segundo o Decreto-Lei nº 14.334 de 30 de novembro de 1944, posto em vigor no qüinqüênio 1949-1953 alterou seu nome para Redenção da Serra. Seu nome é devido ao fato do município ter libertado seus escravos primeiramente entre os municípios paulistas, a 10 de fevereiro de 1888.

Com isso, sendo o primeiro local paulista a libertar seus escravos, nada mais justo do que designá-lo com um nome que eternizasse o feito grandioso, assim surgiu o nome Redenção.

A construção da grande represa do Paraitinga, em ligação com Paraibuna ocorrida no começo da década de 70, obra necessária, porém de inusitadas implicações, determinou o desaparecimento de Natividade da Serra e Redenção da Serra.

Da velha Redenção da Serra, cheia de tradições e fatos históricos, uma parte bastante característica não será atingida pelas águas que invadem a parte baixa de sua topografia; é a situada na parte mais alta: a Igreja Matriz, o sobrado com sacadas de ferro que sediava a Prefeitura e outros poucos sobrados e residenciais da rua Capitão Alvim, que restaram como "memória urbana".

Entre 1976 e 1979 a População e a prefeitura lutaram pela preservação destes remanescentes de Redenção Velha, conseguindo entre outras coisas, um aterro e um muro erguido em torno da Igreja. A concluSão das obras de conservação foi feita pela CESP.

"Quando em 25 de agosto de 1974, o bravo povo redencense erguia numa colina o cruzeiro que simbolizaria o renascimento da cidade, uma página da História seria virada. Não era apenas uma cidade centenária que iria desaparecer, coberta pelas águas da represa da CESP, era uma nova a surgir".