Несмотря на блестящий успех, с которым была произведена высадка, в дальнейшем предстояло немало серьезных затруднений. Арабы имели на Крите укрепленные города, и столица арабского эмира Хандак, неподалеку от Кнососа, представляла собой сильное укрепление. Нужно было овладеть открытой страной и затем начать осаду городов; все это требовало времени и хорошей организации, кроме того, предстояло обеспечить византийский отряд против неожиданных высадок с моря, если бы сирийские или египетские арабы захотели подать помощь своим критским собратьям. Словом, византийскому стратигу следовало многое предусмотреть, чтобы воспользоваться счастливым началом. И нужно сказать, что не везде улыбалось ему счастие. Стратигу фракисийской фемы Никифору Пастиле поручено было сделать разведку в неприятельской стране. Отряд его предался грабежу и без всякой осторожности рассеялся по стране, «обильной пажитями, скотом, всякими плодами». Этим воспользовались арабы и неожиданным нападением почти совершенно истребили неосторожный отряд. Сам предводитель погиб в жаркой схватке. Понимая очень хорошо, что этот успех может сопровождаться весьма тяжелыми последствиями для начатого им похода, если не исправить его новым геройским поступком, который бы подействовал на арабов, Никифор решил немедленно идти на Хандак. Византийское войско шло по прекрасно обработанной и культурной стране, занятой частию христианами, хотя и обращенными в мусульманство, но с распростертыми объятиями принимавшими византийцев, частию арабами, которые спешили укрыться в горы. Подступив к Хандаку, или нынешней Кандии, Никифор должен был оценить неприступное положение крепости, защищенной, с одной стороны, высокой скалой, с другой — морем, которую нельзя было брать силой, так как при естественной защите она была окружена стенами, по которым могли разъезжаться две повозки. Город был снабжен значительным гарнизоном и обеспечен съестными припасами. При таких условиях Никифор Фока не мог приступить к городу и взять его открытой силой. Нужно было решиться на правильную осаду и принудить его к сдаче голодом. В этом смысле и принят был ряд мер. Со стороны моря предоставлено было действовать флоту, который не только отрезал город от морских сношений, но и наблюдал за тем, чтобы извне не была ему подана помощь. Со стороны суши осаждающий отряд окружил город глубоким рвом и валом, так что, с одной стороны, защитил себя этим от неожиданных вылазок и нападений врага, с другой — совершенно изолировал его от сношений с мусульманами, населявшими остров. Вместе с тем главнокомандующий рассылал мелкие отряды во всех направлениях, чтобы опустошать страну, подчинять грекам города и селения и подвозить припасы для осаждающих Хандак войск. Прежде чем было закончено обложение города, эмир Абд-ель-Асиз уведомил африканских и испанских арабов об угрожавшей ему опасности, но помощи ему не было оказано. Осада затянулась на долгое время и поставила осажденных в отчаянное положение — начал ощущаться недостаток припасов. Хотя на выручку осажденным составился отряд в 40 тысяч человек, но Никифор узнал своевременно об его приближении и частию рассеял его, частию перебил на пути к Хандаку. Это обстоятельство, о котором осажденные скоро были оповещены выставленными напоказ под стенами города отрубленными головами арабов, повергло осажденный город в крайнее смущение, лишив его всякой надежды на внешнюю помощь. Хотя под влиянием суровой погоды в зиму 960/61 г. и недостаточного урожая Никифор испытывал большие лишения в самых необходимых предметах, но Иосиф Вринга принял экстренные меры, чтобы критское войско было снабжено всеми нужными запасами, и тем предупредить упадок военной дисциплины. Имея точные сведения через преданных ему людей о том, что делается в городе, Никифор узнавал заблаговременно о готовившихся вылазках, принимал соответствующие меры и наносил хандакскому гарнизону одно за другим сильные поражения. Весной 961 г., сделав надлежащие приготовления к нападению на городские стены, Никифор назначил приступ, который, однако, был отбит и сопровождался большими потерями для осаждавших. В начале марта сделана была новая и уже более решительная попытка овладеть городом. Для этого прежде всего употреблены были подкопы и применены заготовленные заранее стенобитные машины. Лев Диакон дает понять, каким образом был взят наконец город.