Jusuf s’était persuadé qu’il lui était possible d’arriver à Constantine avec l’aide seule des indigènes, sans le concours des troupes françaises, et, chose plus étrange, il avait presque réussi à faire partager au maréchal cette folle confiance. Comme noyau de son futur bataillon, il avait amené d’Alger deux cent quatre vingts coulouglis ; pour recruter le surplus, il comptait sur son nom et sur son prestige. N’était-il pas un des héros de la surprise de Bône ? N’était-il pas populaire ? N’avait-il pas bonne mine sous son riche costume ? Et ses spahis, et ses coulouglis n’avaient-ils pas également bon air? En dépit de la popularité, du costume et de la bonne mine, le recrutement languissait; afin de l’activer, le bey envoya ses chaouchs dans les cafés, dans les boutiques, dans les carrefours, faire la presse et racoler des volontaires. Aussitôt il n’y eut qu’un cri parmi les indigènes : Jusuf était-il donc bey de Bône? Ils coururent aux magistrats, au commissaire civil, qui leur donnèrent raison. Jusuf fut contraint de relâcher sa capture; avec elle disparut aussi sa popularité dans la ville, il essaya de se revancher au dehors. Une proclamation qui sommait les cheikhs de venir rendre hommage à sa dignité fut répandue dans les tribus environnantes ; les plus rapprochées obéirent; les plus éloignées hésitèrent, demandèrent à réfléchir ou s’excusèrent. Au nombre de celles-ci étaient les Ouled Radjeta; le bey résolut de faire sur eux un exemple qui déciderait les autres. A la tête de ses coulouglis, il surprit quelques-uns de leurs douars et s’en revint avec sept cents bœufs et mille moutons ; un peu après, il renouvela l’exemple sur les Ouled Attia. Quelques jours plus tard, on apprit que Ouled Radjeta et Ouled Attia avaient plié leurs tentes et décampé pour aller s’établir loin du bey français, hors de ses atteintes. C’était tout le contraire de ce qu’obtenait jadis le général d’Uzer; mais aussi les procédés de Jusuf étaient tout le contraire des siens.
Un mois à peine après son arrivée, il était bien déchu dans l’estime publique. « Joseph, écrivait à cette époque un correspondant de Duvivier, Joseph est ici, encore plus qu’à Alger, couvert d’or et de diamans ; il a à sa porte deux chaouchs ; mais l’idée que le maréchal lui a promis plus qu’il ne voulait et pouvait tenir, l’arrêt mis au recrutement de son corps et surtout la gêne où des emprunts répétés le réduiront incessamment, ôtent à sa figure cette expression de sérénité, ou plutôt de vanité satisfaite. L’enthousiasme général s’est calmé ; l’opinion publique, devenue silencieuse, laisse percer les haines et les jalousies particulières ; Dieu sait si Joseph en a amassé sur son passage à Oran et pendant son séjour ici ! Les chasseurs d’Afrique et le colonel en particulier sont fort mal avec lui, surtout depuis que sa politique envers les Arabes le fait recevoir un peu froidement et peu rechercher dans la société des officiers
