Между войнами и походами вспыхнула страстная любовь Нечволодова к польской графине Тышкевич. Они поженились, но нечасто им удавалось быть вместе — муж воевал, был ранен и контужен, подлечившись, снова вставал в строй. В 1813 году Нечволодов опять в чине майора воевал в Павлоградском гусарском полку. Под Лейпцигом произвел несколько блестящих атак, вскоре вернул себе прежние суворовские награды и получил новые.
И тут снова вмешалась судьба-злодейка: Григорий Иванович был азартный игрок (а кто тогда не играл!) и однажды просадил 17 тысяч казенных денег. Его опять разжаловали и направили на Кавказ, рядовым в Нижегородский полк. Военный министр писал при этом Ермолову, командиру Отдельного Кавказского корпуса: «Желательно, однако, чтобы Нечволодова не так скоро производили в чины».
Нечволодов и тут отличился в боях, так что сам Ермолов просил о его полном и безусловном прощении. Однако Нечволодова произвели только в прапорщики. Тогда хитрый Ермолов прикомандировал Григория Ивановича к линейным казакам, а у казаков свое начальство и свое чинопроизводство. И через четыре года Нечволодов вернул себе все награды и чин майора.
И вот, когда он служил с казаками, жена написала ему, что, поскольку детей у них нет, она хотела бы удочерить сироту, может быть, девочку-черкешенку. Тогда-то Нечволодов и обратил внимание на Катю. Не известно, как он сумел уговорить казака, но вскоре Катя переехала к нему на квартиру. Катя были живой и впечатлительной девочкой. Как и Григорий Иванович, она с нетерпением ждала приезда приемной матери. Вскоре графиня Тышкевич наконец приехала, и новая семья объединилась. Графиня полюбила девочку, а Катя так и сияла от радости, не отходила от приемной матери ни на шаг. Но общее их счастье длилось недолго. Нечволодову нужно было возвращаться в полк, который стоял в Кахетии. Дорога была долгой и тяжелой. По пути, во Владикавказе, его супруга графиня Тышкевич скоропостижно скончалась от разрыва сердца…
Нечволодов с воспитанницей поселились в местечке Царские Колодцы, неподалеку от Караагача, где стоял Нижегородский полк. Катя сразу сделалась всеобщей любимицей и, как вспоминали, «дочерью полка в полном смысле слова». Среди офицеров-нижегородцев было немало блестяще образованных людей, Катю учили Лев Сергеевич Пушкин, младший брат великого поэта, ссыльные декабристы П. А. Бестужев, Д. А. Искрицкий, А. Е. Рынкевич. А девочка оказалась на редкость прилежной ученицей.
