The first appearance was as a serialized novel, published in The Windsor Magazine, December 1904 through October 1905. Maurice Greiffenhagen created 52 illustrations. The Popular Magazine serialized this novel in 8 parts, January 1905 through August 1905. I do not know if this serialization was illustrated or not.
McKay, Scott, and Whatmore claim that Ward, Lock, and Company published the first edition in book-form in London on October 6, 1905. Apparently 25,000 copies were printed, with 32 of Greiffenhagen's 52 illustrations, but no ads at the end.
Higgins claims that Ward, Lock paid £1,100 ($191,000 in 2020 dollars) for the serial rights, and £1,000 ($173,000 in 2020 dollars) as an advance for publication in book-form.
Doubleday and Company published the first American edition October 6, 1905. There are no ads at the end of the book, and only 8 of Greiffenhagen's original 52 illustrations are included on plates. McKay and Scott both agree on the publication date in New York.
See the VisualHaggard.org page dedicated to the illustrations found in various editions.
David Frank provided the following images and information
Author's proof copy of the first British Printing. Dated November 30, 1904 on the first leaf, while the first printing was published on October 6, 1905. In plain brown paper wrappers, this proof differs from the first printing with the dedication page dated 1904 compared to 1905, the author's note does not include the final paragraph, illustrations are not included, and the text is one page shorter. Of particular note is that the text starting at the bottom of page 373 differs from that of the first printing. London: Ward, Lock, and Co. (1904), 383 pages.
I own the complete serialization of this novel in THE WINDSOR MAGAZINE, but the copies shown below are not mine.
Two of the Greiffenhagen illustrations from the serial
I do not own the serialization of this novel in THE POPULAR MAGAZINE. The first three covers shown below all depict AYESHA, by different artists.
Copies of the British first edition, pictured below. None are mine, though I do own a copy.
Below: Multiple Variant first edition bindings
Variant Colonial first edition binding
Below, a first Canadian edition, with unique red-hued frontispiece
Notice, the frontispiece says upwards, instead of downwards.