Odată ce aranjamentele de răscumpărare pentru captivii mecani au fost finalizate, Muhammad și-a îndreptat atenția către Banu Qaynuqa, considerat cel mai slab, dar și cel mai bogat dintre cele trei triburi evreiești din Medina. Motivele asediului variază în funcție de sursele musulmane. O versiune descrie o altercație care i-a implicat pe Hamza și Ali în piața Banu Qaynuqa, în timp ce o altă narațiune adunată de Ibn Ishaq povestește despre o femeie musulmană care a fost hărțuită de un aurar Qaynuqa. Această hărțuire a escaladat atunci când o farsă a lăsat-o umilită, determinând un bărbat musulman să intervină și să-l omoare pe aurar, ceea ce a dus apoi la moartea bărbatului ca răzbunare. Indiferent de cauza specifică, incidentul a declanșat tensiuni între musulmani și Qaynuqa.
Ca răspuns, Banu Qaynuqa s-au retras în fortăreața lor, unde Muhammad și forțele sale au asediat, întrerupându-le accesul la hrană și provizii. Qaynuqa au căutat ajutor de la aliații lor arabi, dar niciunul nu a venit, deoarece arabii erau din ce în ce mai aliniați cu Mahomed. Asediul a persistat aproximativ două săptămâni înainte ca Qaynuqa, recunoscând izolarea lor, să se predea fără luptă.
După capitularea lor, Muhammad a căutat inițial să-i execute pe oamenii tribului. Cu toate acestea, Abdullah ibn Ubayy, un șef proeminent Khazraj și recent convertit musulman, a mijlocit în numele lor. Ibn Ubayy, care a primit anterior sprijin din partea Qaynuqa, l-a îndemnat pe Mahomed să dea dovadă de clemență. Când Muhammad a refuzat, Ibn Ubayy s-a ținut fizic de mantia lui Muhammad și a insistat până când Mahomed a cedat. Deși furios de perseverența șefului, Muhammad i-a cruțat în cele din urmă pe Qaynuqa, cu condiția ca aceștia să părăsească Medina în termen de trei zile, renunțând la avere și proprietățile lor musulmanilor. Mahomed a păstrat o cincime din prada, așa cum era de obicei.
La scurt timp după expulzarea lui Qaynuqa, tensiunile din Medina au continuat să fiarbă. Ka'b ibn al-Ashraf, o figură bogată a Banu Nadir și un critic vocal al lui Mahomed, se întorsese de la Mecca, unde plânsese înfrângerea Quraysh la Badr printr-o poezie provocatoare. Versurile sale i-au plâns pe cei căzuți și i-au îndemnat pe Quraysh să se răzbune, aprinzând și mai mult ostilitățile dintre musulmani și adversarii lor. Când Muhammad a aflat de acțiunile lui Ka'b, și-a adunat adepții și a întrebat: *„Cine mă va scăpa de Ka'b, care L-a jignit pe Dumnezeu și pe mesagerul Său?”* Ibn Maslamah s-a oferit voluntar, avertizându-l pe Mahomed că sarcina va necesita înșelăciune. Muhammad a consimțit fără obiecții.
Ibn Maslamah a adunat complici, inclusiv fratele adoptiv al lui Ka'b, Abu Naila, pentru a ajuta la executarea planului. Sub pretextul greutății în urma convertirii lor la islam, ei s-au apropiat de Ka'b și i-au câștigat încrederea, convingându-l să le împrumute mâncare. Când l-au întâlnit sub acoperirea nopții, Ka'b, prins neprevăzut, a fost ademenit în afara casei lui. În timp ce mergeau împreună, conspiratorii au lovit brusc, ucigându-l pe Ka'b înainte ca acesta să poată reacționa.