Aussitôt arrivé, Bugeaud reçut la visite de Ben-Durand, qui lui fut présenté par le général de Brossard et qui était porteur d'une lettre d'Abd-el-Kader où celui-ci paraissait manifester le désir de traiter. Il fit connaître au Juif ses conditions, à savoir la reconnaissance de la souveraineté de la France et la fixation de limites précises à la région dont Abd-el-Kader serait laissé maître. Ces premières bases étaient conformes aux instructions que Bugeaud avait reçues du cabinet; elles furent envoyées à Paris par le télégraphe et le général reçut l'autorisation de traiter à ces conditions, que le roi se réservait de ratifier. Mais, lorsque cette dépêche parvint à Bugeaud, il avait déjà perdu en grande partie l'espoir d'un arrangement, car, portées à la connaissance d'Abd-el-Kader, les bases indiquées avaient été aussitôt repoussées. Le général modifia ses premières propositions et accorda à l'émir le Titteri, contrairement aux instructions du cabinet.

L'émir, de son côté, entra en négociations avec Damrémont, espérant, en menant ainsi deux négociations parallèles, obtenir de l'un des généraux ce que l'autre lui refuserait. Cette ruse, si familière aux indigènes, eut un plein succès. Bugeaud, furieux, échangea avec Damrémont des lettres très vives. Durand se vantait de son côté de prendre l'argent d'Abd-el-Kader pour diviser et corrompre les khalifas français, l'argent des khalifas français pour corrompre les conseillers d'Abd-el-Kader. Les plaintes et les récriminations des deux généraux mettaient le ministère dans l'embarras; il décida que la conduite des négociations serait laissée à Bugeaud, sauf approbation du gouverneur général.

De ces négociations résulta le traité de la Tafna (30 mai 1837), par lequel la France se réservait seulement Alger, Oran, Mostaganem, Mazagran et leur banlieue; autour d'Alger, le Sahel et la Mitidja " bornée à l'Est jusqu'à l'Oued Keddara et au delà ".