Finalmente fece imprigionare i conti dell'Aquila, di Caserta, di san Severino e di Tricarico, accusati di non essere andati in suo ajuto contro i Saraceni della Sicilia con quel numero di truppe che dovevansi dai loro feudi; ed in tal modo terminò d'abbattere l'indipendenza feudale de' suoi baroni l'anno 1222.
      Lo stato della Sicilia era ridotto in assai peggiore condizione. I Saraceni e per l'odio che portavano ai Cristiani, e perchè oppressi da insopportabili contribuzioni, eransi ribellati: occupavano essi le montagne del centro dell'isola, e sotto la condotta d'un loro patriotta, detto Mirabet, saccheggiavano la valle di Mazara. La vicinanza dell'Africa facilitava loro i soccorsi de' patriotti, che, accostumati ne' deserti di Barbaria a vivere di ladroneccio, s'affrettavano di venire nella Sicilia a dividerne le spoglie. Federico gli attaccò vigorosamente; e, dopo averli più volte battuti (1223), offri loro nuove terre ne' suoi stati e campagne fertili, ma lontane dal mare, a condizione che gli rinnovassero il giuramento di fedeltà e servissero nelle sue armate. Più migliaja di Saraceni accettarono l'offerta, mentre altri ostinaronsi nella difesa delle loro montagne. Federico trasportò i primi nella Puglia, ove diede loro la città di Lucera colle belle campagne della Capitanata514. Si pretese che questa prima colonia potesse, al bisogno, somministrargli venti mila soldati. Ventiquattro anni dopo ridusse gli altri Saraceni di Sicilia a stabilirsi ad eguali condizioni in una ricca valle tra Napoli e Salerno, ove occuparono la città di Nocera, che di poi conservò sempre l'aggiunto di Nocera dei Pagani.