Word searches (WSs) have been widely studied in L1 and L2 interaction but have rarely been combined with fluency research. The present study bridges the gap between these research fields by examining WSs and their connections to fluency in L1 and L2 dialogue data. From a larger project, 50 participants’ dialogues (25 L1 Finnish, 25 L2 English) were analyzed for WSs. The mixed-methods analyses focused on potential differences and connections in WS use across the L1 and L2 dialogues and the connections between WSs and fluency among selected participants. The results demonstrated differences especially in the use of solitary WSs across L1 and L2 and some connections between L1 and L2 WSs among individual participants, despite group-level connections not being statistically significant. The qualitative analyses illustrated the potential fluency-enhancing functions of collaborative WSs. The study has implications for L2 speech fluency research and L2 teaching.