Sexuality in the marine araphid diatom Tabularia involves an unusual type of gamete, not only among diatoms but possibly in all of nature. The non-flagellated male gamete is free and vigorously motile, propelled by pseudopodia. However, the cues (if any) in their search for compatible female gametes and the general search patterns to locate them are unknown. We tracked and compared male gamete movements in the presence and absence of receptive female gametes. Path linearity of male movement was not affected by presence of female gametes. Male gametes did not move towards female gametes regardless of their proximity to each other, suggesting that the detection range for a compatible mate is very small compared to known algal examples (mostly spermatozoids) and that mate recognition requires (near) contact with a female gamete. We therefore investigated how male gametes move to bring insight into their search strategy and found that it was consistent with the predictions of a random-walk model with changes in direction coming from an even distribution. We further investigated the type of random walk by determining the best-fit distribution on the tail of the move length distribution and found it to be consistent with a truncated power law distribution with an exponent of 2.34. Although consistent with a Lévy walk search pattern, the range of move lengths in the tail was too narrow for Lévy properties to emerge and so would be best described as Brownian motion. This is somewhat surprising because female gametes were often outnumbered by male gametes, thus contrary to the assumption that a Brownian search mode may be most optimal with an abundant target resource. This is also the first mathematically analysed search pattern of a non-flagellated protistan gamete, supporting the notion that principles of Brownian motion have wide application in biology.