22 декабря 1856 года С. А. Шереметев отчислен от полка с назначением состоять для особых поручений при главнокомандовавшем Кавказской армией. В 1858 году с 22 июня по 1 сентября С. А. Шереметев находился в экспедиции лезгинского отряда в непокорные общества: Анцух-Капучу, Анцроссо, Ухнада, Богнада, Иланхеви и Дидо; причем были следующие дела и перестрелки: 12 июня при взятии завалов на ур. Зикари-Кат, 15 – на высотах Жеко; 16 – взятие штурмом сильных неприятельских укреплений на высотах Гарух-Меор; 18 – при взятии Атцухской крепости Гетыны-Ген, причем взято 2 орудия; 19 – при переправе через р. Сара-Ор и взятии штурмом аула Ток; 20 июля – при взятии аулов: Колда, Мачара и Кабасида; 22 – при движении отряда из Атцуха к аулу Калаки, по ущелью р. Хвон-Ор; 25 – при движении части отряда от урочища Закари-Кат на высоты Тинача; 1 августа при взятии завалов на высотах Чумакало; 2 – при переправе через р. Черель-Ор и занятии Анурасского аула Тлафата; 5 – при взятии и разорении Богнадальских аулов: Цикиль и Никар; 12 – при совершенном поражении партии наибов Багазского и Иланхезского на высотах Бала-Кури; 18 – при взятии и разорении Иланхевских аулов: Эшигля и Генатля; 20 августа при взятии штурмом сильно укрепленного и упорно защищаемого Иланхевского аула Китури. С. А. Шереметев, вызвавшись в охотники с 3-й стрелковой ротой лейб-гренадерского Эриванского Его Величества полка для взятия штурмом башен и саклей, наиболее способствовавших упорной обороне и сильно защищаемых горцами, несмотря на жестокий неприятельский огонь, первым ворвался в аул и, приняв после убитого прапорщика князя Микеладзе начальство над первым взводом 3-й стрелковой роты, выбил горцев из нескольких башен и саклей и тем дал возможность занять и зажечь большую часть аула. За этот выдающийся подвиг храбрости С. А. Шереметев Всемилостивейше награжден орденом св. Георгия 4 ст. В 1859 году 24 марта за отличие по службе он был произведен в штабс-ротмистры, с 21 июня по 26 июля находился в отряде в Чечне под личным начальством главнокомандовавшего Кавказской армией; в том же году 6 августа С. А. Шереметев назначен флигель-адъютантом к Его Императорскому Величеству и 9 августа переведен в лейб-гвардии конно-гренадерский полк с переименованием в штабс-капитаны и с оставлением в звании флигель-адъютанта. В 1860 году военная деятельность С. А. Шереметева, произведенного в капитаны, переносится на правый фланг, в пределы нынешней Кубанской области, где в составе главного Шапсугского отряда он участвовал в следующих делах и перестрелках. 20 апреля на рекогносцировке левого нагорного берега Кубани в направлении на р. Иль; 21 – в балке Катлямиджы при выборе места для устройства промежуточного редута; 24 – при передвижении отряда с Кубани на р. Иль; 25 – на рекогносцировке между р.р. Илем и Азипсом; 27 – в перестрелке при движении отряда по р. Иль и в жарком деле при штурме части аула Кабаниц; 28 – в перестрелке при прочистке места для лагеря; 29 – на рубке леса и разработке дороги; 1 мая – в жарком деле при занятии остальной части аула Кабаниц и движении двух колонн в глубь страны, для рубки просек; 2 – в перестрелке при фуражировке; 8 – в перестрелке на рубке леса по правому берегу р. Иль и на фуражировке; 9 – при движении отряда к аулу Эмпсихиако и при занятии его; 12 – в перестрелке на рубке леса у передового редута и при уничтожении близлежащего аула; 15 – при рубке просеки в направлении на р. Убин и при движении легкой колонны на позицию у аула Кабаниц; 16 – при рубке просеки на р. Убине; 17 – на рубке просеки по Анапской дороге; 18 – в деле при рубке леса на обеих сторонах р. Убина и при взятии с боя аулов на этой же реке; 20 – в перестрелке при рубке просеки на р. Убине. Затем – перейдя в состав среднешапсугского отряда, С. А. Шереметев участвовал в следующих делах и перестрелках: 25 мая – на рубке леса по направлению от урочища Эмпсихиако на р. Азипс; 27 – при отбитии партии горцев, бросившихся на место водопоя; 30 – на рубке просеки в направлении на р. Азипс; 6 июля – при уничтожении пластунами двух аулов во время рубки строевого леса на р. Убине и при фуражировке на р. Азипсе; 9 – при отступлении пластунов от разоренного ими аула в ущелье р. Иль и при возвращении колонны с р. Кубани на урочище Кабаниц; 10 – при занятии аулов, лежащих вправо от дороги, разрабатываемой на р. Убине; 14 – при уничтожении аулов вдоль р. Иль. С 15 мая по 4 июня С. А. Шереметев участвовал во всех движениях колонн, высылавшихся из отряда на фуражировки, рубку леса, и проч.; 5 июля он находился при истреблении аулов, лежащих близ вновь проложенной дороги на р. Кубань; 10 июля участвовал в деле при отбитии стада скота на р. Убине; 11 – в жарком деле при истреблении аулов: Кияб, Боргуж и Кушо-Хабль; 16, 19 и 20 июля – в перестрелках на фуражировках; 31 – в деле при набеге части отряда в долину между р.р. Азипс и Хабль, для уничтожения собранных горцами хлебных запасов, отбития скота и истребления большого аула Каразук; с 23 по 30 июля в незначительных перестрелках с колоннами, посылаемыми для рубки леса на фуражировки и для конвоирования на р. Кубань обоза; 6, 7, 11, 13, 14, 15, 18 и 19 августа в перестрелках в колоннах, посылавшихся на фуражировки и на рубку хвороста и за деловым лесом на р. Кубань к посту Великолагерному; 23 сентября при отбитии партии, бросившейся на наш пикет; 25 – при разорении двух больших аулов в долине р. Азипса; 7 ноября – при набеге для разорения хуторов, лежащих по р. Убину; 30 – при передвижении отряда от Ильского укрепления на урочище Тучуз-Маше; 1 декабря при рекогносцировке Анапской дороги и на фуражировке в долине Богай; и 3 – при уничтожении большого аула Пшижиатук на р. Азипсе. 11 июля 1861 года Сергей Алексеевич был переведен в Кубанское казачье войско подполковником с оставлением в звании флигель-адъютанта и в том же году 13 сентября за отличие в делах с горцами награжден золотой шашкой с надписью за «храбрость», за таковое же отличие 28 октября Всемилостивейше пожалован орденом св. Станислава 2 ст. с мечами, а 13 ноября назначен командиром 13 полка Кубанского казачьего войска.