Arthur Conan Doyles first significant work was A Study in Scarlet which appeared in Beeton's Christmas Annual .
I may be wrong but the very first detective story has always been considered to be The Murders in the Rue Morgue by Edgar Allan Poe.
Have a look here..there are a few earlier ones http://encarta.msn.com/encyclopedia_761559994/Detective_ Story.html
The Murders in the Rue Morgue is a short story written by Edgar Allan Poe in 1841.
The Moonstone (1868) by Wilkie Collins is a 19th-century novel, generally considered the first detective novel in the English language.
So I agree with the others on The Moonstone ,as this is a novel rather than a short story.
I had entirely forgotten about Wilkie Collins.
It's my age you know !