Gradasso è il primo dei capi saraceni a comparire nel poema cavalleresco di Matteo Maria Boiardo; re di Sericana e del popolo arabo dei Nabatei, giunge con un immenso esercito attraverso l'India, la Persia, l'Arabia, l'Africa in Spagna per combattere contro il re Marsilio soccorso da Carlo Magno ma, dopo un duello con Rinaldo, rimasto interrotto a causa di una miracolosa scomparsa di quest'ultimo, si accorda con Marsilio per invadere la Francia. Tutti i paladini cristiani e lo stesso Carlo finiscono suoi prigionieri. Gradasso decide così di chiedere come riscatto Baiardo, il cavallo di Rinaldo, e la spada Durlindana del paladino Orlando. Ottenuto il consenso del monarca franco si vede sfidato dallo stravagante eroe cristiano Astolfo, che incredibilmente lo batte, costringendolo quindi a ripiegare in Oriente.

Nell'Orlando Furioso di Ludovico Ariosto Gradasso perde l'alone favoloso presente nell'opera precedente e diventa un semplice cavaliere saraceno dotato però di una forza e di un valore eccezionali, un "saracino Marte" come lo definisce Ariosto nel Canto XLI, stanza 68. Gradasso nel poema ottiene i suoi oggetti del desiderio: infatti durante uno scontro tra due fazioni dell'esercito saraceno fa sua la spada Durlindana, mentre poco dopo, imbattutosi in Rinaldo, riprende il duello interrotto nell’Innamorato e si impossessa di Baiardo. Il re saraceno approda infine sull'isola di Lipadusa per supportare il re Agramante offrendosi come compagno contro il paladino Orlando. Qui riesce ad uccidere Brandimarte, ma perirà subito dopo a sua volta per mano di Orlando.