Using a free-recall paradigm, we explored the effects of age of acquisition and category size on verbal fluency in Turkish Sign Language (Türk Isaret Dili [TID]). We studied the semantic and phonological fluency task performances of deaf native and deaf late adult signers. We measured the number of correct responses and performed a time course analysis to observe how signers engage in lexical retrieval. Each task parameter had three difficulty settings corresponding to the size of the selected phonological and semantic categories. The results show that native TID signers produced more correct responses. However, the results reveal no relation between the age of acquisition and the retrieval rate since participants maintained close subsequent response times. This indicates that participants had similar lexical access. Furthermore, the number of signs that the participants produced decreased as the level of difficulty (as a function of category size) increased. Therefore, phonological and semantic category size was found to be a suitable measure for categorical difficulty in TID. We conclude that both groups of signers update information in the working memory and engage in lexical access similarly, but delayed acquisition of TID results in a smaller search set in the mental lexicon.