В сентябре 1831 г. Кривцова известили о "высочайшей милости" - переводе на Кавказ рядовым в 44-й егерский полк, где для него спустя десять лет снова началась военная жизнь. Служба проходила на Черноморском побережье: Сухуми, Гагра, Бомборы (вблизи Гудаут), изредка наезжал в Тифлис. Места эти "славились" тогда сырым губительным климатом, ужасной смертностью, страшной малярией и другими болезнями. Сергей Иванович болел несколько раз, а потом всю жизнь страдал астмой. В эти годы Кривцов выучил грузинский язык, занимался переводами грузинских авторов. В августе 1834 г. его определяют в Ставрополь, где стояла 20-я артиллерийская батарея. Здесь же жила племянница София (дочь сестры Варвары), она была замужем за М. Бибиковым, адъютантом генерала А. Вельяминова, и в их доме С. Кривцов всегда находил приют вплоть до своей отставки весной 1839 года.
Три последующих года, с весны до осени, прошли в многочисленных военных экспедициях, сражениях и стычках, где он подвергался ежедневным опасностям. В письме к братьям в Сибирь в декабре 1835 г. писатель-декабрист А. Бестужев-Марлинский отмечал: "В отряде со мной был Кривцов. Под ним убита лошадь картечью, ибо у горцев есть артиллерия". В другом письме А. Бестужев-Марлинский упоминает: "Сергей Иванович кланяется вам, кто его помнит или знает".
За кампанию 1835 г. Кривцов был произведен в унтер-офицеры.
Сослуживец Сергея Ивановича офицер И. Фондер-Ховен тепло отзывался о нем: "Высокий ростом, плечистый, с черными кудрявыми волосами... Умный в разговоре, приятный в обществе и храбрый в деле, он невольно обращал на себя внимание... В делах я имел случай несколько раз прикрывать егерями его два горных единорога, которыми он командовал и с коими он всегда был впереди, а так как опасности, труды и лишения похода сближают людей, то я с ним скоро сошелся и всегда находил отраду в приятной с ним беседе".
Как отмечалось в приказе, 26 августа 1837 г. Кривцов проявил храбрость и мужество в бою, "производя меткие выстрелы картечью из одного легкого орудия". К этому времени он уже получил солдатского Георгия и ждал производства в офицеры. В октябре 1837 г. в Ставрополе Сергей Иванович познакомился с М. Лермонтовым. Факт известный. В Лермонтовской энциклопедии сказано, что Михаил Юрьевич, находясь в первой ссылке, по пути из Тамани в Тифлис задержался в Ставрополе, где на квартире Н. Сатина и познакомился с декабристом. Им было о чем поговорить. Оба храбрые офицеры, служили на Кавказе, оба в юности воспитывались в Московском университетском пансионе.
