The efficacy of video-based sign language (SL) navigation aids to improve Web search for Deaf Signers was tested by two experiments. Experiment 1 compared 2 navigation aids based on text hyperlinks linked to embedded SL videos, which differed in the spatial contiguity between the text hyperlink and SL video (contiguous vs. distant). Deaf Signers' performance was similar in Web search using both aids, but a positive correlation between their word categorization abilities and search efficiency appeared in the distant condition. In Experiment 2, the contiguous condition was compared with a text-only hyperlink condition. Deaf Signers became less disorientated (used shorter paths to find the target) in the text plus SL condition than in the text-only condition. In addition, the positive correlation between word categorization abilities and search only appeared in the text-only condition. These findings suggest that SL videos added to text hyperlinks improve Web search efficiency for Deaf Signers.