The novel starts when Sherlock Holmes receives a mysterious book ciphered message from an agent to Professor Moriarty using the pseudonym Fred Porlock. Holmes deduces the book used for encryption to be a monthly almanac; however, he initially uses the latest publication, which leads him to decipher Porlock's message as a statement that the "Maharata Government is pigs bristles." Upon realizing his error and using the previous month's almanac, Holmes successfully deciphers the message as a warning that "some deviltry is intended against one Douglas", a country gentleman residing at Birlstone Manor. Simultaneously, Inspector Macdonald arrives at Baker Street with news that Mr. Douglas has in fact been murdered. Holmes tells MacDonald of Porlock's warning, suggesting Professor Moriarty's involvement. However, MacDonald doesn't fully believe that the educated and well respected Moriarty is a criminal.
Holmes, Watson, and MacDonald travel to Birlstone, Sussex, where they investigate the old manor with a moat where Douglas was shot. They meet Cecil Barker, a regular guest of the Douglas. They also find a sawed-off shotgun and evidence suggesting that it was fired at close range, causing the head to be blown to pieces. Holmes explores Barker's claims that he was in his room when Douglas was shot. Moreover, they find a mark of blood upon the window sill suggesting someone entered and escaped by going through the moat. Beside the body they find a card with the initials "V.V. 341", and on Douglas's arm an old branded mark. Moreover, Douglas' wedding ring appears taken from his hand.
The police speculate that if the murderer must have escaped across the moat, but if this was so then the question of his clothes were wet as he walked through the town. Holmes establishing the timeline of events through interviews: Cecil Barker heard the shot, rushed down to the study and upon seeing Douglas murdered he rang the servants. Mrs. Douglas and the servants rushed to the scene. Mr. Barker persuades Mrs. Douglas to return to her room. Holmes notes Mrs. Douglas apparent lack of emotion over her husband's body.
Barker says that he believes a secret society of men pursued Douglas, and that Douglas retreated to rural England out of fear for his life. Mr. Douglas married after arriving in England five years earlier. His first wife had died of typhoid. Douglas met and worked with Cecil Barker in America, before departing for Europe. Some episode of Douglas's life in America caused the fear for his life, and Mrs. Douglas said her husband mention something called "The Valley of Fear".
By studying Cecil Barker's slippers, Holmes determines Barker's shoe made the mark on the window, to give the appearance that someone exited that way. In their lodgings, Holmes tells Watson that Cecil Barker and Mrs. Douglas are certainly lying: when a shotgun is fired at close range, the sound is muffled. Moreover, Holmes learns that the housekeeper heard a door slamming half an hour before the alarm, which Holmes believes was actually the murdering shot. White Mason, the Sussex detective, and MacDonald track a bicycle found on the grounds of the house to an American staying at a guest house. The American appears to be the murderer, but there is no sign of the man.
Holmes ask MacDonald to write to Cecil Barker, telling him that the police intend to search the moat the next day. That night Holmes, Watson, MacDonald and White lay in wait outside Birlstone Manor and see Cecil Barker fish something out of the moat. The four men rush Cecil and discover the bundle from the moat contain the clothes of the missing American connected with the bicycle. Barker refuses to explain the situation. At that moment, Mr. Douglas appears, alive and well. He hands Watson a written account called "The Valley of Fear", which explains why he feared for his life.
Douglas explains that he had spotted an enemy of his, Ted Baldwin, in the area and expected an attack. When Baldwin attempted to shoot him in his study, Douglas grabbed the gun and shoots Baldwin in the face. With Cecil's help, Douglas dressed the man in his own clothes, except for his wedding ring, to deceive the secret society which he and Baldwin had belong too, since both arms bore the society's Mark. Cecil and Mrs. Douglas had covered for Douglas who had been hiding in the house. In an interview with Watson, Douglas explains that his real name was Birdy Edwards acting as Pinkerton detective in Chicago. For the agency Edwards infiltrated a dangerous gang in Vermissa Valley (a.k.a. the Valley of Fear) and brought them to justice. Afterwards, the criminals attempted to kill him, after being released from jail.
Hounded Douglas had run to England, where he met and married his second wife. Holmes urges Douglas to leave England and warns that a new threat now hangs over him. Douglas takes this advice, but shortly after Holmes learns that Douglas was lost overboard on the vessel to Africa. Holmes believes Moriarty was responsible for ending Douglas' life. Holmes wants to bring Moriarty down, but warns Watson and Barker that it will take some time to achieve.

Question: Where do Holme's Watson, and Macdonald travel?
Answer: Birlstone, Sussex
Alternative answer: Birlstone, Sussex