There is evidence from at least two independent sources that in 1855, not long after he arrived in the Malay Archipelago, Wallace began to write notes for a book about evolution. It is thought that its provisional title was "The Organic Law of Change", and it seems that he abandoned work on it in 1859 when he found out that Darwin was about to publish a book on the same subject i.e. On the Origin of Species. Interestingly, Darwin had begun writing his book on evolution in 1856 about a year after Wallace started writing notes for his book.
The notes for Wallace's book survive in a difficult-to-interpret notebook in the library of The Linnean Society, a scanned version of which the Society intends to put up on the web soon. The notebook has been carefully transcribed and is being meticulously studied by a colleague, who has almost finished writing a book about the evolution of Wallace's evolutionary ideas, which will be published later this year.
For more information about Wallace's planned book on evolution see McKinney, H. L. 1972. Wallace and Natural Selection. New Haven & London: Yale University Press. 193 pp.