L'auteur de l'ouvrage fut souvent recherché afin de le situer dans le cadre de l'Histoire de la rhétorique. Les indices chronologiques situent la rédaction du texte entre 344/343 et 300 av. J.-C.[5]. Mais plusieurs problèmes se posent.
Au début du traité, est présente une lettre dédicatoire d'Aristote pour adresser l'ouvrage à un de ses élèves, Alexandre le Grand. C'est de là que vient le titre conventionnel des manuscrits médiévaux et l'attribution à Aristote, avec sa présence dans le corpus aristotélicien[4]. Selon cette lettre, le traité fut aussi coécrit avec Corax. Il fut établi que cette lettre est une forgerie, probablement écrite au IIe siècle de notre ère [6]. Cette lettre, du courant de la seconde sophistique pour augmenter la valeur du traité, devait être convaincante au moins sur le contexte, malgré des erreurs évidentes, notamment du fait que ce n'est pas dans les usages littéraires du IVe siècle av. J.-C. Bien que les philologues à l'époque moderne jugent une imitation médiocre et une imposture flagrante — le professeur Werner Jaeger parle d'un auteur « […] naïf, totalement dépourvu de sens historique […] »[7] —, aucun témoignage jusqu'à l'époque médiévale ne conteste son authenticité. Cette lettre permet au traité d'être inclus dans le corpus d'Aristote, permettant sa probable survie mais aussi sa déformation[8]. En plus de la lettre, plusieurs preuves permettent de conclure qu'Aristote n'a pas écrit ce traité, on lui en refuse l'attribution depuis Érasme[9]. Malgré plusieurs ressemblances[10], la Rhétorique diverge sur de nombreux points, ainsi que sur l'idéologie de la rhétorique d'Aristote exposée dans Phèdre, visant une rationalisation de la persuasion qui n'est pas présente ici, d'autant que la Rhétorique à Alexandre est écrit à la première personne du singulier, ce que ne fit pas Aristote[11] et elle n'est pas présente dans les anciens catalogues de ses œuvres[12]. La référence dans la lettre au Theodectia, un traité de jeunesse perdu d'Aristote sur Théodecte de Phasélis peut expliquer cette attribution car les ressemblances sont fortes mais les témoignages sont trop imprécis pour confirmer l'hypothèse[13].
Le rhéteur Corax n'est connu que par des citations trop brèves ou une tradition byzantine qui remit en question son rôle, on ne peut déterminer son rôle mais ce n'est probablement pas son œuvre[14]. Quant à l'hypothèse de l'ouvrage composite, elle est rejetée car si on remarque de nombreuses redites, incohérences et un vocabulaire hétérogène, c'est plutôt la marque d'un seul auteur qui utilisa un amalgame de documents mal synthétisés[15].
L'hypothèse a été parfois retenue d'une attribution à Anaximène de Lampsaque, en raison des citations de Quintilien et Syrianos, d'autant que les genres et le nombre des natures oratoires concordent[16]. Le problème est l'état du texte tel qu'il nous est parvenu. À la fin du XIXe siècle furent découverts à El Hibeh plusieurs papyrus, dont l'un (PHib. 26, l'un des plus longs mais avec de nombreuses lacunes[17], sigla Π pour l'établissement du texte) était le traité de rhétorique ici présent. On remarque ainsi de nombreuses différences par rapport à la tradition manuscrite qui nous est parvenue[18]. Le texte a subi de très nombreuses altérations et interpolations au fil de sa retranscription avant l'époque médiévale, les principales modifications portent sur la formulation des genres, les « catégories » et globalement, les rédacteurs voulaient harmoniser la doctrine du traité avec celle d'Aristote, auquel on prête la paternité de la Rhétorique à Alexandre[19]. Des philologues tentèrent de reconstituer le traité originel en essayant de repérer les principales interpolations mais le texte fut grandement refondu, la reconstitution du texte originel est improbable, les informations sur sa rédaction sont trop limitées[20]. On peut donc conclure que si on se base sur la citation de Quintilien, l'ouvrage est d'Anaximène avec la restriction que le texte dont il parle est largement différent de celui qui est connu par la tradition manuscrite[21].
