Советская верхушка — начиная с Варенникова и ниже, руководившая военными действиями в Афганистане, нашла полное понимание со статным и общительным Наджибуллой, который представлял собой полную противоположность Кармалю — не только своим телосложением, но и характером. Так, Варенников считал «Наджиба», хорошо говорившего по-английски и поверхностно знавшего французский, хорошо образованным и политически проницательным лидером. Наджибулла, бывший одним из основателей фракции «Парчам» в НДПА был внуком пуштунского вождя племени, таким образом сочетая в себе оба важных качества для того, чтобы стать авторитетной фигурой в Афганистане, и к тому же очень любил власть. При Амине Наджибуллу отослали послом в Иран прежде, чем отправить в отставку и лишить гражданства. Он вернулся в Афганистан после советского вторжения. Здесь он снова жадно включился в политические игры и, как начальник службы безопасности, прославился участием в пытках и казнях. При правлении Кармаля его влияние продолжало расти — отчасти благодаря его успешным действиям по вытеснению с политической арены сил царандоя, которые находились под началом возглавляемого Гулябзоем министерства внутренних дел, бывшему оплотом фракции «Хальк» в НДПА, которая противостояла «парчамистам». После того, как в 1985 году следователи ХАД приступили к арестам офицеров царандоя, обвинив их в антисоветской деятельности, в январе 1986 года было сформировано министерство государственной безопасности, одной из задач которого было наблюдать за отдельными подразделениями царандоя. (Министерство Гулябзоя пережило эти репрессии, однако самого Гулябзоя президент Наджибулла продолжал считать одним из своих главных соперников. После серии стычек, в 1988 году Гулябзой был отправлен в Москву в качестве посла Афганистана).
Наджибулла также извлек свою выгоду и из событий в Пакистане. В конце 1985 года пакистанское правительство организовало ряд нападений на пуштунских лидеров некоторых племен в граничащей с Афганистаном Северо-Западной Пограничной провинции, где практически не действовали никакие законы. Наджибулле удалось укрепить свой авторитет среди пуштунов, пообещав поддержку и оружие их оскорбленным военным вождям. Варенников полагал, что у Наджибуллы были большие шансы добиться «национального примирения» в Афганистане, которое советский командующий считал ключевой предпосылкой для стабилизации конфликта и выводу советских войск. В ходе одной из первых из его многочисленных встреч с «Наджибом» и его главным советским консультантом Виктором Поляничко, все трое согласились использовать для этой цели 580 военных контрольно-пропускных пунктов на дорогах Афганистана, на каждом из которых постоянно дежурило по нескольку десятков советских и афганских солдат. Поскольку эти пункты напрямую взаимодействовали с большей частью местного населения, Варенников считал, что они могли бы распределять пищу, топливо, мыло и другие предметы обихода среди афганцев с целью свести к минимуму поддержку моджахедов со стороны местных жителей. Но препятствием для этих и других усилий по укреплению авторитета правительства оставалась советская оккупация. Популярность Наджибуллы в сельской местности была не намного больше, чем у его предшественника Кармаля.
Тем не менее, Советы продолжали одерживать все новые победы в войне. Разрозненные группировки моджахедов, неспособные действовать сообща, могли лишь обороняться. Военные усилия Москвы по-прежнему мало помогали достигнуть окончательной цели, а именно — помочь дружественному коммунистическому правительству эффективно управлять Афганистаном. Война затянулась еще на пять тяжких лет, в течение которых повстанцы с помощью умелой бравады и иностранной помощи продолжали свое сопротивление силам, намного превосходившим их собственные. Боевые действия стали еще более напряженными в течение того года, который Горбачев предоставил военным на завершение войны. На очередном съезде Коммунистической партии в Москве в феврале 1986 года он заявил, что «контрреволюция и империализм превратили Афганистан в кровоточащую рану».
Тремя месяцами позже, в мае 1986 года, Организация Объединенных Наций, которая с 1982 года выступала посредником в продвигавшихся с трудом переговорах между правительствами Афганистана и Пакистана, помогла организовать мирные переговоры между Советами и моджахедами. Во время встречи на высшем уровне в Женеве в ноябре 1985 года новый советский лидер Горбачев ясно дал понять Рейгану, что он серьезно относится к выводу советских войск из Афганистана и предложил новый срок — через четыре года. И все же, переговоры не привели к какому бы то ни было соглашению. Вскоре Горбачев объявил о частичном одностороннем выводе советских сил из Афганистана, численность которых к тому времени выросла до 115 000. Он заявил о выводе 6000 из них. Правда, американская разведка утверждала, что в то время как некоторые советские воинские соединения действительно вернулись домой, на смену им в Афганистан в том же году было отправлено еще 9000 советских солдат.